三（四）元环计数

发表于
又是不会的科技

无向图三元环计数

将边定向，度数少的点连向度数多的点，度数相同时编号小的连向编号大的。这样保证一个点它的出度不会超过 $ O(\sqrt{m}) $ （因为原本度数大于 $ \sqrt{m} $ 的点不会超过 $ \sqrt{m} $ 个）。
然后暴力。对于每个$u$，找$ v \in e[u] $, $ w \in e[v] $ ,若 $ w \in e[u] $ 那么找到三元环。一个个数就行。

无向图四元环计数

和无向图三元环计数一样将边定向，不同的是计数方式会麻烦一点。
定向后四元环会出现两种情况：
$$
1 \rightarrow 2, 2 \rightarrow 3, 3 \rightarrow 4, 1 \rightarrow 4\
1 \rightarrow 2, 2 \rightarrow 3, 1 \rightarrow 4, 4 \rightarrow 3
$$
考虑通过对角$2, 4$ 计数。先将点按照定向后的图拓扑排序。先对于每一个$2$，找$ 1 \in ee[2] $, $ 3 \in ee[2] $, $ 4 \in e[1] $, $ 4 \in e[1] $, $ 4 $的拓扑序在$2$后，其中ee代表的是原图的边，e代表的是定向后的边。开个数组统计。

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

代码

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
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int mod = 1e9 + 7;
const int N = 2e5 + 10, M = 5e5 + 10;
int n, m, d[N], id[N], rnk[N];
int ex[M], ey[M];
vector<int> e[N], ee[N];
int cnt3 = 0, cnt4 = 0;
bool vis[N]; int num[N];

void solve() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) {
		e[i].clear(), ee[i].clear();
		vis[i] = 0, num[i] = 0;
		cnt3 = cnt4 = 0;
		d[i] = 0;
	}
	for(int i = 1; i <= m; i++) {
		scanf("%d%d", &ex[i], &ey[i]);
		++d[ex[i]], ++d[ey[i]];
		ee[ex[i]].pb(ey[i]), ee[ey[i]].pb(ex[i]);
	}
	for(int i = 1; i <= m; i++) {
		int x = ex[i], y = ey[i];
		if(d[x] > d[y] || (d[x] == d[y] && x > y)) swap(x, y);
		e[x].pb(y);
	}
	for(int i = 1; i <= n; i++) {
		for(auto v : e[i]) vis[v] = 1;
		for(auto u : e[i]) for(auto v : e[u]) if(vis[v]) ++cnt3;
		for(auto v : e[i]) vis[v] = 0;
	}
	for(int i = 1; i <= n; i++) id[i] = i;
	sort(id + 1, id + n + 1, [&](int x, int y) { return d[x] != d[y] ? d[x] < d[y] : x < y; });
	for(int i = 1; i <= n; i++) rnk[id[i]] = i;
	for(int i = 1; i <= n; i++) {
		for(auto u : ee[i]) for(auto v : e[u]) if(rnk[v] > rnk[i])
			cnt4 = (cnt4 + num[v]) % mod, num[v]++;
		for(auto u : ee[i]) for(auto v : e[u]) if(rnk[v] > rnk[i]) num[v] = 0;
	}
	printf("%d %d\n", cnt3, cnt4);
}
int main() {
	int T; scanf("%d", &T);
	for(; T; --T) solve();
}

有向图三（四）元环计数

先将边看作无向边，枚举（统计）环的时候再判断方向即可。

竞赛图找三元环

只要不是拓扑图就有三元环。

竞赛图三元环计数

容斥。
$$
Ans = C(n, 3) - \sum_{i=1}^{n}C(d_i, 2) \space d_i表示i点的出度
$$