acm-无向图三元环、四元环计数_无向图四元环

三元环计数

考虑对无向图的边进行定向，度数小的点连向度数大的点，如果度数相同则编号小的点连向编号大的点。
然后再这张新图(有向图)中我们枚举所有点$u$，对于每个点$u$我们枚举它的出边对应的端点$v$，先给这些点打上标记，然后再枚举$u$的出边对应的端点$v$，枚举$v$的出边对应的端点$w$,如果$w$是标记点的话就找到一个三元环，每个三元环都一定只会被恰好枚举一次，因此找到一个三元环就$++ans$即可，注意枚举下一个$u$之前需要清空标记数组。

考虑正确性，经过重定向后新图一定是一张无环的有向图，那么三元环只可能是如下图所示的形式：

容易发现只有再枚举$A$的时候能够将该三元环计入答案。

由于枚举$u,v$复杂度为$O(n+m)$，考虑对于每个$v$而言，假设它的出边有$k$条，那么$deg[v]\ge k$，那么这$k$条边对应的端点$w$的度数也一定至少为$k$，因此$k\ast k\le 2m\Rightarrow k=O(\sqrt{m})$，即总复杂度约为$O((n+m)\sqrt{m})$。

这里以LuoGu P1989 无向图三元环计数为例给出一份参考代码：

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5+5;
const int maxm = 2e5+5;

struct EDGE{
	int u,v;
}e[maxm];
int vis[maxn],deg[maxn];
vector<int>g[maxn];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;++i){
		scanf("%d%d",&e[i].u,&e[i].v);
		deg[e[i].u]++;
		deg[e[i].v]++;
	}
	for(int i=0;i<m;++i){
		int u=e[i].u,v=e[i].v;
		if(deg[u]>deg[v])swap(u,v);
		if(deg[u]==deg[v] && u>v)swap(u,v);
		g[u].push_back(v); 
	}
	int ans=0;
	for(int u=1;u<=n;++u){
		for(int v:g[u])vis[v]=1;
		for(int v:g[u])for(int w:g[v])vis[w]&&(ans++);
		for(int v:g[u])vis[v]=0;
	}
	printf("%d\n",ans);
} 
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

四元环计数

类似于三元环，我们也要对原图进行重定向，不过这里需要保留原图，设$g$是原图，$h$是新图，我们仍然枚举$u$，然后再原图中枚举$v$，然后在新图中枚举$w$，如果$w$的优先级大于$u,v$，那么先把答案加上$w$的统计量$cnt[w]$，然后再$cnt[w]++$即可。

容易发现复杂度与三元环是一样的，唯一的区别在于标记和统计答案的方式不同。核心原理是把四元环拆成两半，下面给出具体解释。
我们发现$h$图中的每个四元环一定存在一个端点是如下形式：

即在这个环中至少有两条边指向同一个顶点，上图中除了这两条边外的另外两条边，假设他们没有指向同一个顶点，比如像下图这样：

那么可以发现只有枚举到$A$点的时候才会统计到该四元环，具体来说会先走$A->B->C$统计一半，再走$A->D->C$统计另一半，注意走第一条边的时候走的是原图的边！如果以$AC$为轴线存在多个四元环，那么按照这种一半一半统计贡献的方式仍然是可以全部计算出来的。另外注意到新图$h$中存在$A->B->C$这样的拓扑链，说明$A$的优先级是小于$C$的，因此也能确保循环的能够进入最里层。

再看一种特殊情况，那就是存在两个点都是两条边的指向，如下图所示：

上图中$A、C$两点都是被两条边所指向的点，好像这个四元环会被统计两次，但实际上不会，因为$A、C$必定存在一个优先级的大小之分(计算度数相同还要比较编号)，因此仍然只会被统计一次。

综上来说每个四元环都恰好被一个点统计一次，因此算法是正确的，复杂度分析与三元环的相同，就不多说了。下面给出一份参考代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
int d[maxn],id[maxn],rk[maxn],cnt[maxn];
vector<int>g[maxn],h[maxn];

int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;++i)d[id[i]=i]=g[i].size();
	sort(id+1,id+1+n,[&](int a,int b){
		return d[a]<d[b] || d[a]==d[b] && a<b; 
	});
	for(int i=1;i<=n;++i)rk[id[i]]=i;
	for(int u=1;u<=n;++u)for(auto v:g[u]){
		if(rk[v]>rk[u])h[u].push_back(v);
	}
	int ans=0;
	for(int u=1;u<=n;++u){
		for(auto v:g[u])for(auto w:h[v])if(rk[w]>rk[u]){ans+=cnt[w]++;}
		for(auto v:g[u])for(auto w:h[v])if(rk[w]>rk[u])cnt[w]=0;
	}
	printf("%d\n",ans);
}/*test:
6 6
1 2
1 3
2 4
3 4
3 6
2 5
*/
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