不常用的黑科技——「三元环」

同步于cnblogs

同步于hexo博客

可能会有一些n,m之类的混淆，如果造成阅读障碍欢迎打脸

万恶之源：

给定一张无重边、无自环的无向图

点数为n，边数为m，且n,m同阶

问有多少个无序三元组(i,j,k)，使得存在：

1. 有一条连接i,j的边
2. 有一条连接j,k的边
3. 有一条连接k,i的边

举个例子：

这张图中有三个三元环：(1,2,3),(1,3,4),(3,4,5)

有一个显然的基于度数的乱搞的做法（本人并没有写过……），可以在这里阅读到：jiachin_zhao 三元环计数

这里介绍一种十分优秀的三元环计数方法：

首先要对所有的无向边进行定向，对于任何一条边，从度数大的点连向度数小的点，如果度数相同，从编号小的点连向编号大的点

此时这张图是一个有向无环图

之后枚举每一个点u，然后将u的所有相邻的点都标记上“被u访问了”，然后再枚举u的相邻的点v，然后再枚举v的相邻的点w，如果w存在“被u访问了”的标记，那么(u,v,w)就是一个三元环了

而且每个三元环只会被计算一次

那么现在就只需要证明三件事：

1. 定向后的图是一个有向无环图

以上图为例，用deg_u表示u在原图中的度数，则deg_a \ge deg_b \ge deg_c \ge deg_d \ge deg_e \ge deg_a

既deg_a=deg_b=deg_c=deg_d=deg_e=deg_a

对于度数相同的点，是按照编号从小到大连边的，则a \le b \le c \le d \le e \le a

既a=b=c=d=e

然而点的编号是1 \sim n的全排列，因此不会产生如上的事情，既不存在环

由于这张图有向，而且没有环，因此这张图就是有向无环图

2. 时间复杂度是O(m \sqrt m)（在此认为n,m同阶）

对于“打标记”这个操作，每个点都会将所有的出边遍历一遍，那么这里的时间复杂度为O(n+m)

对于访问u，然后访问v，然后访问w，可以这么考虑：对于每条边（u \rightarrow v），对时间复杂度的贡献为out_v，其中out_v表示v的出边个数

这样就转化为了求\sum_{i=1}^{n}out_i

不妨将out_v分类讨论

1. out_v \le \sqrt m$，那么由于$u$连接$v$，因此$deg_u \ge deg_v$，这样的$u$的个数是$O(n)$的，因此这里的时间复杂度为$O(n \sqrt m)
2. out_v \gt \sqrt m$，那么由于$u$连接$v$，因此$deg_u \ge deg_v$，既$deg_u \gt \sqrt m$，这样的$u$的个数是$O(\sqrt m)$的，因此这里的时间复杂度为$O(\sqrt m m)=O(m \sqrt m)

因此时间复杂度为O(n+m+n\sqrt m+m\sqrt m)=O(m \sqrt m)

3. 每个三元环只会被统计一次

三元环在有向无环图上无非就长这样：

也只能且只会在u处被计算一次

事实上连边的时候从度数小的连向度数大的也可以证明时间复杂度是O(m \sqrt m)……

下面是一个样例程序

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> g[N];
int deg[N], vis[N], n, m, ans;
struct E { int u, v; } e[N * 3];
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1 ; i <= m ; ++ i) {
        scanf("%d%d", &e[i].u, &e[i].v);
        ++ deg[e[i].u], ++ deg[e[i].v];
    }
    for(int i = 1 ; i <= m ; ++ i) {
        int u = e[i].u, v = e[i].v;
        if(deg[u] < deg[v] || (deg[u] == deg[v] && u > v)) swap(u, v);
        g[u].push_back(v);
    }
    for(int x = 1 ; x <= n ; ++ x) {
        for(auto y: g[x]) vis[y] = x;
        for(auto y: g[x])
            for(auto z: g[y])
                if(vis[z] == x)
                    ++ ans;
    }
    printf("%d\n", ans);
}

一些习题