【学习笔记】无向图、有向图的三元环、四元环计数问题（根号分支+bitset）_有向图三元环计数

无向图三元环计数问题

根号分治

记 $d_i:i$ 在原图中的度数。

按照以下规则改写无向图为有向图：

• 对于一条边 $u,v$。
  • 如果两点度数不同，则度数大的指向度数小的。
  • 如果两点度数相同，则编号小的指向编号大的。

「其实只需要定一个有序的规则即可，可以是度数小的指向大的，可以是编号大的指向小的，都不影响。」

显然，这个有向图同时也是个无环图。

证明：

假设存在一个环 $(x_0,x_1,x_2,...,x_k)$。

则有 $d_{x_0}\ge d_{x_1}\ge d_{x_2}\ge ...\ge d_{x_k}$。

即 $d_{x_0}=...=d_{x_k}$。

所以 $x_0<x_1<x_2<...<x_k<x_0$，矛盾。

所以三元环 $(u,v,w)$ 在新图中的边一定是：$u\to v,u\to w,v\to w$。

考虑在 $u$ 点记录这个三元环的贡献。

将所有与 $u$ 直接相连的点打上标记，再从中枚举点作 $v$ ，枚举与 $v$ 直接相连的点 $w$ ，检查 $w$ 是不是 $u$ 指向的点即可。

时间复杂度为 $O(m\sqrt{m})$。

证明：

将枚举 $w$ 的复杂度记在 $u\to v$ 边上，显然为 $ou{t}_v$ 。「$ou{t}_v:v$ 的出度」

则总复杂度为 ${\sum }_{(u,v)\in E}ou{t}_v+{\sum }_{u}ou{t}_u$

• 若 $ou{t}_v<\sqrt{m}$，则复杂度为 $O(m\sqrt{m})$。

• 若 $ou{t}_v>\sqrt{m}$，因为有向图的连边规则，有 $ou{t}_u\ge ou{t}_v>\sqrt{m}$。

原无向图的总边数为 $m$，所以这样的 $(u,v)$ 仅有 $\sqrt{m}$ 个，复杂度为 $O\sqrt{m}$。

#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
#define maxm 200005
vector < int > G[maxn];
int n, m;
int d[maxn], Eu[maxm], Ev[maxm], vis[maxn];

bool cmp( int x, int y ) {
    return d[x] == d[y] ? x < y : d[x] > d[y];
}

int main() {
    scanf( "%d %d", &n, &m );
    for( int i = 1;i <= m;i ++ ) {
        scanf( "%d %d", &Eu[i], &Ev[i] );
        d[Eu[i]] ++, d[Ev[i]] ++;
    }
    for( int i = 1;i <= m;i ++ )
        if( cmp( Eu[i], Ev[i] ) ) G[Eu[i]].push_back( Ev[i] );
        else G[Ev[i]].push_back( Eu[i] );
    int ans = 0;
    for( int i = 1;i <= n;i ++ ) {
        for( int j : G[i] ) vis[j] = i;
        for( int j : G[i] )
            for( int k : G[j] ) 
                if( vis[k] == i ) ans ++;
    }
    printf( "%d\n", ans );
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

bitset

bitset 其实是一种二进制的优化。

只要想要的信息可以转化为被 $0/1$ 表示出来，在空间不炸的情况下，bitset 自带 $/\omega$ 的复杂度。

将与 $i$ 点直接相连的所有点对应在 $i$ 的 bitset 中位置置为 $1$，表示两点有边相连。

然后就直接枚举每条边，将边的两个端点的 bitset 取个 &，就得到了与两点均直接相连的所有点集合。

空间复杂度为 $O(n^2)$ ，来自 bitset。

时间复杂度为 $O(\frac{nm}{\omega })$。

如果有些题目空间比较卡，不能直接硬开。

其实是给每个点很大一段的 $0$ 开完整 bitset 空间就会被大幅度浪费。

那么就可以设定一个阈值 $B$「分块的阈值」。

对于度数 $>B$ 的点就开完整的 bitset，这种点不会超过 $\min (n,\frac{m}{B})$ 个。

度数 $\le B$ 的点就直接暴力枚举连边，暴力判断。

所有度数 $>B$ 的点最多会被 $O(m)$ 条边枚举到，一次计算是 $O(\frac{m}{\omega })$，时间复杂度为 $O(\frac{nm}{\omega })$。

度数 $\le B$ 的点的贡献是 $d^2$，则有 ${\sum }_d\le m,d\le B$，总共为 $\sum d^2\le B\cdot m$。

时间复杂度为 $O(\frac{nm}{\omega }+B\cdot m)$，空间复杂度就降为了 $O(\frac{nm}{B})$。

「根据具体题目的时空灵活选取阈值 $B$，在不甚了解三元环的根号分治时，bitset 这种优美的暴力来的快也好写/doge」

无向图四元环计数问题

同样按照三元环计数问题的方法来建立有向图，并给每一个点分配唯一的 $rank$ 排名。

则一个四元环在新图中至少有一个，至多有两个度数为 $2$ 的点。

这时会发现原图的四元环 $(u,v,w,x)$ 在新建的有向图中会有两种情况。

• $u\to v\to w,u\to x\to w$
• $u\to v\to w\to x,u\to x$

发现这两种形式都可以由 两条无向边+两条有向边 形式表示。

所以一个四元环唯一的表示为：$u-v\to w,u-x\to w$，且 $rank(u)$ 最小，$rank(w)$ 最大，这样才能保证一个四元环不被反复计算。

枚举点 $u$，枚举其在原图的出边 $v$，枚举 $v$ 的在新图上所有出边 $w$，且要满足 $rank(u)<rank(v)<rank(w)$。

先 $ans\leftarrow cn{t}_w$，再 $cn{t}_w++$，最后 $u$ 更换的时候，所有 $cnt$ 都要清零。

在上述过程中，$cn{t}_w:w$ 的入度，且 $rank(w)$ 最大 $rank(u)$ 最小，那么当有两组 $(u,v_1,w),(u,v_2,w)$ 的时候代表找到了一个四元环。

虽然环有对称性，但这样处理后一个四元环只会从 $u$ 算到 $w$ 上。

时间复杂度为 $O(m\sqrt{m})$。证明与三元环一样。

#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
vector < int > G[maxn], E[maxn];
int n, m;
int d[maxn], id[maxn], rnk[maxn], cnt[maxn];

int main() {
    scanf( "%d %d", &n, &m );
    for( int i = 1, u, v;i <= m;i ++ ) {
        scanf( "%d %d", &u, &v );
        E[u].push_back( v );
        E[v].push_back( u );
        d[u] ++, d[v] ++, id[i] = i;
    }
    sort( id + 1, id + n + 1, []( int x, int y ) { return d[x] == d[y] ? x < y : d[x] > d[y]; } );
    for( int i = 1;i <= n;i ++ ) rnk[id[i]] = i;
    for( int i = 1;i <= n;i ++ ) for( int j : E[i] ) if( rnk[j] > rnk[i] ) G[i].push_back( j );
    int ans = 0;
    for( int i = 1;i <= n;i ++ ) {
        for( int j : E[i] ) for( int k : G[j] ) if( rnk[k] > rnk[i] ) ans += cnt[k], cnt[k] ++;
        for( int j : E[i] ) for( int k : G[j] ) cnt[k] = 0;
    } 
    printf( "%d\n", ans );
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

有向图三四元环计数问题

按照无向图的方法做，求出一个元环后直接随便选一个点开始左右两个方向都走一圈，看能不能回到开始点，就知道无向图上的元环能否用原有向图上的边构造出来。