三元环

发表于 更新于 分类于

三元环个数

可以看看这篇文章不常用的黑科技——「三元环」
给每条边定向，度数不同的大度数向小度数连边，度数相同编号小的向大连边。
这样会生成一个有向无环图。
直接搜索每个点\(u\)的相邻的点，打上标记是被谁(u)访问的。
搜索每个点相邻的点的相邻点，如果某个点被\(u\)访问过了，说明这是一个三元环。

因为每个三元环都长这样
>[图片来源]((https://www.luogu.com.cn/blog/KingSann/fou-chang-yong-di-hei-ke-ji-san-yuan-huan-post)

所以每个三元环只被统计一次。

例题

Counting Stars

这道题需要知道每条边在多少个三元环上，所以每次找三元环时给边打上标记。
建图的时候记录下\(u\)，\(v\)之间的边。
最后的答案就是\(\sum\limits_{i=1}^{m}\binom{cnt-i}{2}\)

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
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

const int N = 3e5 + 5;
int cnt[N], deg[N], vis[N], x[N], y[N], n, m;
vector<pair<int, int> > e[N];

int main() {
    while (scanf("%d %d", &n, &m) != EOF) {
		for (int i = 1; i <= m; i++) {
			scanf("%d %d", &x[i], &y[i]);
			deg[x[i]] += 1;
			deg[y[i]] += 1;
		}
		for (int i = 1; i <= m; i++) {
			int u = x[i], v = y[i];
			if (deg[u] < deg[v] || (deg[u] == deg[v] && u > v)) swap(u, v);
			e[u].push-back({v, i});
		}
		for (int u = 1; u <= n; u++) {
			for (auto v : e[u]) vis[v.first] = v.second;
			for (auto v : e[u])
				for (auto w : e[v.first]) {
					if (vis[w.first]) {
						cnt[w.second]++;
						cnt[v.second]++;
						cnt[vis[w.first]]++;
					}
				}
			for (auto v : e[u]) vis[v.first] = 0;
		}
		long long res = 0;
		for (int i = 1; i <= m; i++) {
            res = res + cnt[i] * 1ll * (cnt[i] - 1) / 2;
		    cnt[i] = 0;
		}
		for (int i = 1; i <= n; i++) e[i].clear(), deg[i] = 0;
		printf("%lld\n", res);
	}
	return 0;
}

构造三元环图

题目链接

有一种构造方式是每个点给编号更小的点连边，知道有\(n\)个三元环为止。
\(k\)个点时，三元环个数是\(\sum\limits_{i=3}^{k}\binom{i-1}{2}\)
考虑\(k\)到某个大小时，三元环个数与\(n\)尽量接近且不大于\(n\)
这时候再继续连边，连\(i\)条边会增加\(\binom{i}{2}\)个三元环。
所以无论如何最终都可以凑成\(n\)个三元环。
--话说\(k\)的大小怎么证明啊？--

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

int n, k = 1;
int a[606][606];

int main() {
    scanf("%d", &n);
	for (int i; n; n -= (i - 1) * (i - 2) / 2, k++) {
        for (i = 1; i < k && (i - 1) * i / 2 <= n; i++) a[i][k] = 1;
	}
	printf("%d\n", k - 1);
	for (int i = 1; i < k; i++, puts(""))
		for (int j = i + 1; j < k; j++) printf("%d ", a[i][j] | a[j][i]);
	return 0;
}