图论小记
三元环计数
无向图三元环计数指在 \(G=(V,E)\) 中有多少个无序点对 \((x,y,z)\) 满足 \((x,y),(y,z),(x,z) \in E\).
首先，我们将无向图转化成有向图，设 \(d_i\) 表示 \(i\) 的度数，我们按照 \(d_i\) 从小到大排序（相同则按编号从小到大），然后每条边由排在前的指向排在后的。
不难发现，原图中的三元环在新图中必然是 \(x\) 指向 \(y\) 和 \(z\)，\(y\) 指向 \(z\) 的形式。
所以我们枚举 \((x, y)\) 这条边，然后枚举所有 \(y\) 的出边指向节点 \(z\)，判断 \(z\) 是不是 \(x\) 指向的节点。具体实现可以向将所有 \(x\) 指向节点打标记，这样方便判断。
这个做法看似暴力，但是其时间复杂度是 \(O(m\sqrt{m})\) 的，因为我们可以证明新图中每个点的出度不超过 \(2\sqrt{m}\)。
证明不难，反证法，如果 \(d_x > 2\sqrt{m}\)，则所有 \((x,y)\) 的 \(y\) 也会 \(d_y > d_x > 2\sqrt{m}\)，这样总边数就超过了 \(m\)，于是证出这个结论。
这其实也间接证明了三元环的个数不超过 \(m\sqrt{m}\)，所以我们实际可以找出所有的三元环。这在解决一些问题时很有帮助。
例1： P1989 无向图三元环计数
思路：
模板题。
点击查看代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
const int M = 2e5 + 5;
int n, m;
vector<int> e[N];
int d[N] = {0};
typedef pair<int, int> pii;
pii ed[M];
bool cmp(int x, int y) {//x是否在 y 前面
if (d[x] != d[y])
return d[x] < d[y];
return x < y;
}
bool f[N] = {false};
int main() {
cin >> n >> m;
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
d[u]++, d[v]++;
ed[i] = make_pair(u, v);
}
for (int i = 1; i <= m; i++)
if (cmp(ed[i].first, ed[i].second))
e[ed[i].first].push_back(ed[i].second);
else
e[ed[i].second].push_back(ed[i].first);
int ans = 0;
for (int x = 1; x <= n; x++) {
for (auto y: e[x])
f[y] = true;
for (auto y: e[x])
for (auto z: e[y])
if (f[z])
ans++;
for (auto y: e[x])
f[y] = false;
}
cout << ans << endl;
return 0;
}
例2： CF985G Team Players
思路：
不错的计数题。
显然原图的补图边数很多，肯定不能真的建出来找三元环。
考虑先算出所有点对的贡献，再减去不符合要求的点对的贡献。
按照三元环处理套路，还是建出新图，则不符合要求的有三种情况：三元环，一条链，一条边加上一个点。
分别去计数这几类的数量即可，注意一条链在计算时会将三元环算三次，二一条边加一个点会将一条链算两次，三元环算三次，最后要减去这些。
很多细节，代码有点长，不太好写。
例3： 有向图三元环计数问题
思路：
其实很简单，转化成无向图，显然所有有向图的三元环在无向图中还是三元环，找出无向图的三元环再判断即可。
例4： HDU6184 Counting Stars
思路：
不难。求出所有三元环，设 \(c_i\) 表示第 \(i\) 条边被几个三元环包含，答案就是 \(\sum_i \binom{c_i}{2}\)。
例5： #6076. 「2017 山东一轮集训 Day6」三元组
思路：
前置知识：莫比乌斯反演。
看到这种 \(\gcd(i,j)=1\) 的形式就要想到莫反， 我们要计算的就是：
运用莫比乌斯函数和莫反套路，我们可以转化成：
观察这个式子，这题数据范围 \(a,b,c \le 50000\)。
首先，有很多 \(\mu\) 取值都是 \(0\)，我们可以去掉它们。
其次，我们发现只有 \(\operatorname{lcm}(i,j) \le 50000\) 时才有贡献，考虑到这是三个数的问题，我们不妨将所有 \(\operatorname{lcm}(i,j) \le 50000\) 的连一条 \((i,j)\)。
现在我们就是要找出所有的三元环，然后计算贡献即可。
实测最后建出来的边其实不多，大概是 \(3\times 10^5\)，瓶颈在于建图。
我们没必要枚举 \(i,j\)，反过来想，枚举 \(\operatorname{lcm}(i,j)\) 然后枚举其所有因子，在判断是否可行即可。