题解：P1989 【模版】无向图三元环计数

· · 题解

参考资料

题意简述

给定一张简单无向图，求其三元环个数。

解题思路

顶点 x 的度数记为 \deg(x)，入度记为 \operatorname{in}(x)，出度记为 \operatorname{out}(x)。

将每条无向边按两点的 (\deg(x),x) 从小到大定向，得到一张有向无环图（DAG），因为这是 严格全序。

在新图中枚举 u，并按 u\to w 和 u\to v\to w 计数，每个三元环只会被顺序最小的顶点统计 1 次。

考虑每个顶点 v，根据定向规则：

\operatorname{out}(v)\le\deg(v)\le\deg(w),\forall w\in G_v \operatorname{out}(v)^2\le\sum_{w\in G_v}\deg(w)\le 2m \operatorname{out}(v)\le O(\sqrt{m})

因此时间复杂度为：

\begin{aligned} T &= O\left(\sum_u\sum_{v\in G_u}\operatorname{out}(v)\right) \\ &= O\left(\sum_v\operatorname{in}(v)\operatorname{out}(v)\right) \\ &\le O\left(\sum_v\operatorname{in}(v)\sqrt{m}\right) \\ &= O\left(\sqrt{m}\sum_v\operatorname{in}(v)\right)=O(m\sqrt{m}) \end{aligned}

参考代码

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

const int N=200005;
int deg[N],tag[N];
vector<int> G[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<pair<int,int>> a(m);
    for(auto &[u,v]:a)
    {
        cin>>u>>v;
        deg[u]++;
        deg[v]++;
    }
    for(auto [u,v]:a)
    {
        if(make_pair(deg[u],u)>make_pair(deg[v],v))swap(u,v);
        G[u].push_back(v);
    }
    int ans=0;
    for(int u=1;u<=n;u++)
    {
        for(int w:G[u])tag[w]=u;
        for(int v:G[u])for(int w:G[v])if(tag[w]==u)ans++;
    }
    cout<<ans<<'\n';
    return 0;
}