三、四元环计数

• 三元环

  题目链接

  • 题目：

    给定一个$n$个结点$m$条边的无向图，问有多少个三元环。
    $(1\le n\le 10^5,1\le m\le 2\times 10^5)$

  • 题解：

    使用根号分治的思想。
    基于原图的连边，将度数较小的点向度数较大的点连边，如果度数相同，结点编号小的向结点编号大的连边，形成一个新的有向图，显然这个有向图是一个$DAG$（因为从一个结点出发到达的点要么度数比它大，要么结点编号比它大，所以不会回到自己）。那么原图的三元环在新的有向图上一定可以由形如$<u,v>,<u,w>,<v,w>$这样的三条边构成。先枚举点$u$，再枚举点$u$的出边$<u,v>$，然后枚举点$v$的出边$<v,w>$，判断点$w$是不是点$u$的出点，如果是那么就形成了一个三元环，可以在枚举点$u$后先将点$u$的所有出点打上标记，这样就可以$O(1)$判定点$w$是不是点$u$的出点了。
    上述算法的复杂度是$O(m\sqrt{m})$的。首先枚举$u$再枚举$u$的出边的过程相当于枚举了新图所有的边，数量为$O(m)$。对于点$v$，如果$v$在原图的度数小于等于$\sqrt{m}$，那么在新图中的度数不会更多，所以在新图中的度数为$O(\sqrt{m})$；如果$v$在原图的度数大于$\sqrt{m}$，又由于它在新图中只会向度数比它大的结点连边，而这样的结点数量为$O(\sqrt{m})$，所以点$v$在新图中的度数为$O(\sqrt{m})$。所以总的复杂度为$O(m\sqrt{m})$。

  • 复杂度：$O(m\sqrt{m})$

  • 代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<bitset>
#include<sstream>
#include<ctime>
//#include<chrono>
//#include<random>
//#include<unordered_map>
using namespace std;

#define ll long long
#define ls o<<1
#define rs o<<1|1
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
const double pi=acos(-1.0);
const double eps=1e-6;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const int maxn=1e5+5;
ll read(){
	ll x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,m;
vector<int>g[maxn],g2[maxn];
int deg[maxn],vis[maxn];
int main(void){
	//freopen("in.txt","r",stdin);
	scanf("%d%d",&n,&m);
	int u,v;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		g[u].pb(v);
		g[v].pb(u);
		deg[u]++;
		deg[v]++;
	}
	for(int u=1;u<=n;u++){
		for(auto v:g[u]){
			if((deg[u]<deg[v])||(deg[u]==deg[v]&&u<v)){
				g2[u].pb(v);
			}
		}
	}
	ll ans=0;
	for(int u=1;u<=n;u++){
		for(auto v:g2[u])vis[v]=u;
		for(auto v:g2[u]){
			for(auto w:g2[v]){
				if(vis[w]==u){
					++ans;
				}
			}
		}
	}
	printf("%lld\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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

• 四元环

  • 题目：

    给定一个$n$个结点$m$条边的无向图，问有多少个四元环。
    $(1\le n\le 10^5,1\le m\le 2\times 10^5)$

  • 题解：

    按照三元环的方式建出有向图，并按照这个规则给每个结点赋一个排名$rk$，如果还想按三元环的思路往下走会遇到一个问题，就是原图的四元环在新建的有向图中可能有两种形式，
    
    所有需要使用别的枚举方法。可以发现这两种形式都可以由两条无向边+两条有向边表示，即
    
    且两条无向边的替代位置唯一，所以我们可以把原图的四元环当成两段无向边$(u,v)$+有向边$<v,w>$拼起来的，且无论是哪种情况，$r{k}_u<r{k}_w$。先枚举$u$，再枚举原图中$u$的出边$(u,v)$，然后枚举新图中$v$的出边$<v,w>$，令$cn{t}_w$为从$u$出发经过之前提到的有向+无向到达$w$的路径条数，那么如果$r{k}_w>r{k}_u$，答案加上$cn{t}_w$，表示拼接上之前的路径，并且令$cn{t}_w$加1，表示为之后的路径提供贡献，这样可以避免重复计算。复杂度和之前三元环的分析是类似的。

  • 复杂度：$O(m\sqrt{m})$

  • 代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<bitset>
#include<sstream>
#include<ctime>
//#include<chrono>
//#include<random>
//#include<unordered_map>
using namespace std;

#define ll long long
#define ls o<<1
#define rs o<<1|1
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
const double pi=acos(-1.0);
const double eps=1e-6;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const int maxn=1e5+5;
ll read(){
	ll x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,m;
vector<int>g[maxn],g2[maxn];
int cnt[maxn],deg[maxn],id[maxn],rk[maxn];
int cmp(int a,int b){
	return deg[a]<deg[b]||(deg[a]==deg[b]&&a<b);
}
int main(void){
	// freopen("in.txt","r",stdin);
	scanf("%d%d",&n,&m);
	int u,v;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		g[u].pb(v);
		g[v].pb(u);
		deg[u]++;
		deg[v]++;
	}
	for(int i=1;i<=n;i++)id[i]=i;
	sort(id+1,id+n+1,cmp);
	for(int i=1;i<=n;i++)rk[id[i]]=i;
	for(int u=1;u<=n;u++){
		for(auto v:g[u]){
			if(deg[u]<deg[v]||(deg[u]==deg[v]&&u<v)){
				g2[u].pb(v);
			}
		}
	}
	ll ans=0;
	for(int u=1;u<=n;u++){
		for(auto v:g[u]){
			for(auto w:g2[v]){
				if(rk[w]>rk[u])ans+=cnt[w]++;
			}
		}
		for(auto v:g[u]){
			for(auto w:g2[v]){
				if(rk[w]>rk[u])cnt[w]=0;
			}
		}
	}
	printf("%lld\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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84