并非无向图三元环计数 2

dongzirui0817 · 2026-07-08 19:44:33 · 算法·理论

有所听闻 并非无向图三元环计数。所以今天不讲三元环，更不讲 K_4。今天讲 无向图四元环计数。

先导入一下。

一元环计数

等价于自环数，这你肯定会求。

二元环计数

求一下 u,v 之间的重边个数，设有 w 条重边，则它对答案的贡献为 \frac{w(w-1)} 2。用个 map 处理一下重边即可，时间复杂度 O(m\log m)。可以上点手段，比如 gp_hash_table 可以搞成 O(m)。

三元环计数 P1989

去看 这个题解，时间复杂度 O(m\sqrt m)。请一定要学会，因为这是四元环计数的基础。

四元环计数 LibreOJ 191

主角登场。结论是可以做到 O(m\sqrt m)。

和三元环一样，我们还是给边定个方向。度数小的点向度数大的点连边，度数相同时，编号小的点向编号大的点连边。

当然这里度数大连小还是小连大没关系，编号亦然。

然后我们再用现在的有向图建个反图，待会会知道它的作用的。

设四元环由四个点 a,b,c,d 组成，x \to y 表示 x 向 y 连一条有向边。现在，一个四元环有三种可能。

a\to b、b\to d、a\to c、c\to d

此时就是找有多少条 a \to x \to d 的路径，设有 v 条，则对答案的贡献为 \frac{v(v-1)}2。

for (auto v : e[u])
    for (auto w : e[v])
        if (w ^ u) ans += c[w][0], ++c[w][0];

a \to b、b \to c、c \to d、a \to d

其实就是找 a\to x \gets b 的路径数，设有 v 条，则对答案的贡献为 \frac{v(v-1)}2。注意到 a 点和 b 点本质上是一样的，所以答案算完后还要除以 2。

for (auto v : re[u])
    for (auto w : e[v])
        if (w ^ u) ans += c[w][1], ++c[w][1];
ans /= 2;  // 注意，这里 ans 不一定整除 2，这里当 /= 不是整除

可以发现只有这三种情况。做完了。

:::success[Code]

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

const int N = 1e5 + 10, M = 2e5 + 10;

int n, m;
int u[M], v[M], d[N];
vector <int> e[N], re[N];
ll ans = 0, c[N][2];
// 十年 OI 一场空，但实测 int 也能过 
/*
u[i], v[i]：边 (u, v) 
d[i]：i 的度数
e: 有向图
re：反边 
c[i][0]：Case 1, 2
c[i][1]：Case 3 
*/

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1 ; i <= m ; i++) {
        scanf("%d%d", &u[i], &v[i]);
        d[u[i]]++;
        d[v[i]]++;
    }
    for (int i = 1 ; i <= m ; i++) {
        if (d[u[i]] < d[v[i]] || (d[u[i]] == d[v[i]] && u[i] < v[i])) swap(u[i], v[i]);
        e[v[i]].push_back(u[i]);
        re[u[i]].push_back(v[i]);
    }
    for (int u = 1 ; u <= n ; u++) {
        ll t1 = 0, t2 = 0, t3 = 0;
        for (auto v : e[u])     // Case 1
            for (auto w : e[v])
                if (w ^ u) t1 += c[w][0], ++c[w][0];
        for (auto v : re[u])        // Case 2, 3
            for (auto w : e[v])
                if (w ^ u)
                    t2 += c[w][0], t3 += c[w][1], ++c[w][1];
        for (auto v : e[u])     // 清空 
            for (auto w : e[v]) c[w][0] = 0;
        for (auto v : re[u])
            for (auto w : e[v]) c[w][1] = 0;
        ans = ans + t1 * 2 + t2 * 2 + t3;   // 这里把 t1 t2 t3 全乘 2，输出时除以 2 
    }
    printf("%lld\n", ans / 2);
    return 0;
}

::: :::success[省空间版]

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

const int N = 1e5 + 10, M = 2e5 + 10;

int n, m;
int u[M], v[M], d[N];
vector <int> e[N], re[N];
ll ans = 0, c[N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1 ; i <= m ; i++) {
        scanf("%d%d", &u[i], &v[i]);
        d[u[i]]++;
        d[v[i]]++;
    }
    for (int i = 1 ; i <= m ; i++) {
        if (d[u[i]] < d[v[i]] || (d[u[i]] == d[v[i]] && u[i] < v[i])) swap(u[i], v[i]);
        e[v[i]].push_back(u[i]);
        re[u[i]].push_back(v[i]);
    }
    for (int u = 1 ; u <= n ; u++) {
        for (auto v : e[u])     // Case 1
            for (auto w : e[v])
                ans += c[w] * 2, ++c[w];
        for (auto v : re[u])    // Case 2
            for (auto w : e[v])
                if (w ^ u) ans += c[w] * 2;
        for (auto v : e[u])
            for (auto w : e[v]) c[w] = 0;
        for (auto v : re[u])    // Case 3
            for (auto w : e[v])
                if (w ^ u) ans += c[w], ++c[w];
        for (auto v : re[u])
            for (auto w : e[v]) c[w] = 0;
    }
    printf("%lld\n", ans / 2);
    return 0;
}

:::

:::info[时间复杂度证明]{open} 时间复杂度 O(m\sqrt m)，空间复杂度 O(m)。

第一种情况下，v,w 都是正边，和三元环一样。

第二、三种情况下，v 是反边，w 是正边。枚举 v 是 O(m) 的，w 和三元环也一样，是 O(\sqrt m) 的。

所以时间复杂度 O(m\sqrt m)，可以通过。 :::

:::error[for 的顺序不能搞反]{open} 不能 v 枚举正边，w 枚举反边。就是不能这么写：

for (auto v : e[u])
    for (auto w : re[v])
        if (w ^ u) ans += c[w];

这样写当 v 的度数大于 \sqrt m 时，根据建边的方式，w\to v 说明 w 度数小于等于 v 的度数。在原来是大于等于，可以说明 w 的数量小于等于 \sqrt m。现在不能说明了，于是就退化成 O(nm) 了。 :::

你可能会说：“三元环计数我都没咋用，四元环计数岂不更 useless？”

其实还是有点用的但不多，让我们看一下下面这道例题。

:::info[ABC260F Find 4-cycle]{open} 给一个左边 S 个点，右边 T 个点，M 条边的二分图，输出任意一个四元环上的四个点的编号（顺序不限），或报告无解。