本篇主要讨论圈数较小（\(k \leq 5\)） 的时候无向图上数圈的方法。
1.k \(\leq\) 4
这部分可以做到 \(n,m \leq 10^5\) （点数和边数）。
\(k = 2\) ： ？？？不用说。
\(k = 3\)：我们考虑有方向性的数环避免重复，给每个点定义其属性为 \((deg_i,i)\) ，\(deg\) 即无向图度数，比较属性时首先比较第一项。这样我们发现这是一个偏序关系。对于每一条边，都定向为小的指向大的。
容易发现每个三元环都是 \(1 \to 2,2 \to 3,1 \to 3\) （\(1,2,3\) 代表属性从小到大）的形态，所以枚举每一个点作为 \(1\) ，枚举其出边作为 \(2\) ，枚举 \(2\) 的出边作为 \(3\) ，最后判断 \(1,3\) 是否连边即可。
判断很简单，每次枚举 \(1\) 的时候先给出边的点打上 \(tag = i\) ，然后看 \(tag_3\) 是否等于 \(i\) 即可。
看起来很暴力对不对？其实这样是 \(\Theta(m \sqrt m)\) 的，下面解释：
我们考虑每次是枚举了一条边，和这条边出点的出度，尝试证明每个点的出度都是 \(\leq \sqrt m\) 的，我们分讨：
-
如果原来这个点的 \(deg\) 就 \(\leq \sqrt m\) ，那么定向后出度只会小，所以一定在 \(\sqrt m\) 以内。
-
如果大于，那么它只会连向 \(deg_v\) 大于它的 \(deg\) 的 \(v\) 。这样的 \(v\) 一定满足 \(deg_v \geq \sqrt m\) ，不超过 \(\sqrt m\) 个。
所以我们证明了每个点的出度是 \(\Theta(\sqrt m)\) 的，复杂度得证。
模板题 Luogu P1989
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
pair <int,int> e[N];
vector <int> G[N];
int deg[N],vis[N],n,m;
inline int calc3()
{
static int vis[N];
memset(vis,0,sizeof(vis));
int ret = 0;
for(int i = 1;i <= n;i++)
{
for(auto to : G[i]) vis[to] = i;
for(auto to : G[i])
for(auto tw : G[to])
if(vis[tw] == i)
ret ++;
}
return ret;
}
int main()
{
cin>>n>>m;
for(int i = 1,x,y;i <= m;i++) cin>>x>>y,e[i] = make_pair(x,y),deg[x]++,deg[y]++;
for(int i = 1;i <= m;i++)
{
if(deg[e[i].first] > deg[e[i].second]) G[e[i].second].push_back(e[i].first);
else if(deg[e[i].first] < deg[e[i].second]) G[e[i].first].push_back(e[i].second);
else if(e[i].first < e[i].second) G[e[i].first].push_back(e[i].second);
else G[e[i].second].push_back(e[i].first);
}
cout<<calc3();
return 0;
}
\(k = 4\) ：
还是向刚才一样赋一个属性值，这样一个四元环有 \(3\) 种形态：
我们的基本思路是枚举两条边，将它们交汇在一起用桶统计。
由于一定有一个点被两条出边指向，我们考虑这样的思路，从一个点出发，走一条原图的无向边（新图可正可反），再走一条新图的有向边，走到 \(v\) ，将 \(ans += pot_v\) ，再将 \(pot_v++\) 。
（\(pot_v\) 这个是桶，名字 \(pot\) 纪念 xtr Bug_Automation 的个人中心 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)）
我们惊奇的发现，这样做正好能将上面的两种情况统计恰好 \(1\) 次，但是下面的情况会统计 \(2\) 次，怎么办呢？
我们发现统计两次是因为一次从顶上出发，一次从下面出发，所以我们只需要统计时强制规定最后到达的点 \(v\) 的属性大于枚举的 \(x\) 和中间点 \(to\) 就好了，对于前两种情况来说，一定是这样的，对于最后一种情况，顶上和下面一定有一个大于另外一个，就只会统计一次。
时间复杂度 \(\Theta(m \sqrt m)\) ，证明同 \(k = 3\) 。
模板题 LOJ 191
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
vector <int> e[N],G[N];
int deg[N],n,m,pot[N];
inline bool lrg(int x,int y) // x > y ??
{
if(deg[x] ^ deg[y]) return deg[x] > deg[y];
else return x > y;
}
int main()
{
cin>>n>>m;
for(int i = 1,x,y;i <= m;i++) cin>>x>>y,e[x].push_back(y),e[y].push_back(x),deg[x]++,deg[y]++;
for(int i = 1;i <= n;i++)
for(auto to : e[i])
if(lrg(to,i))
G[i].push_back(to);
long long ans = 0;
for(int i = 1;i <= n;i++)
{
for(auto to : e[i])
for(auto tw : G[to])
if(lrg(tw,to) && lrg(tw,i))
ans += pot[tw],pot[tw]++;
for(auto to : e[i])
for(auto tw : G[to])
pot[tw] = 0;
}
cout<<ans;
return 0;
}
一道练习题：CF985G Team Players
给定 \(n\) 点 \(m\) 边无向图，一个三元组如果互相都没有连边，贡献是 \(A * min + B * mid + C * max\) 。求所有三元组贡献和 \(\mod 2^{64}\)。
\(1 \leq n,m \leq 2 \times 10^5\) 。
首先考虑容斥，答案等于 \(f_0 - f_1 + f_2 - f_3\) 。
\(f_i\) 是选三个点，其中至少有 \(i\) 条边的贡献。
\(f_0\) 好求，每个三元组都可以贡献。
\(f_1\) 枚举每条边，在除了 \(u,v\) 外任选一点都可以，讨论大小即可。
\(f_2\) 是一个链（两条边并且相接），考虑枚举中间那个点，将出边按照出点大小排序后扫描，假设当前扫到 \(u,v\) ，讨论对于已经扫描过的出点 \(p\) ，\(p \in [0,\min(u,v) - 1],[\min(u,v) + 1,\max(u,v) - 1],[\max(u,v) + 1,n - 1]\) 中的哪一个即可。
\(f_3\) 就是无向图三元环板子，因为计算时会枚举到三个点，所以可以直接计算。
复杂度 \(\Theta(m \sqrt m)\) 。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef unsigned long long ull;
vector <int> e[N],G[N];
int n,m,deg[N];
ull A,B,C;
inline bool lrg(int x,int y)
{
if(deg[x] ^ deg[y]) return deg[x] > deg[y];
return x > y;
}
inline ull calc0()
{
ull ret = 0;
for(int i = 0;i < n;i++)
{
if(i < n - 1) ret += 1ull * (n - i - 1) * (n - i - 2) / 2 * A * i;
ret += 1ull * i * (n - 1 - i) * B * i;
if(i > 0) ret += 1ull * i * (i - 1) / 2 * C * i;
}
return ret;
}
inline ull sum(int x) {if(x <= 0) return 0; return 1ull * (x + 1) * x / 2;}
inline ull calc1()
{
ull ret = 0;
for(int i = 0;i < n;i++)
for(auto to : e[i])
{
if(to < i) continue;
ret += (1ull * A * i + 1ull * B * to) * (n - 1 - to) + C * (sum(n - 1) - sum(to));
ret += (1ull * A * i + 1ull * C * to) * (to - i - 1) + B * (sum(to - 1) - sum(i));
ret += (1ull * B * i + 1ull * C * to) * i + A * sum(i - 1);
}
return ret;
}
inline ull calc2()
{
ull ret = 0;
for(int i = 0;i < n;i++)
{
ull sig1 = 0,cnt1 = 0,sig2 = 0,cnt2 = 0;
sort(e[i].begin(),e[i].end());
for(auto to : e[i])
{
if(to < i)
{
ret += sig1 + cnt1 * i * C + cnt1 * to * B;
cnt1++; sig1 += A * to;
}
else
{
ret += sig1 + cnt1 * i * B + cnt1 * to * C;
ret += sig2 + cnt2 * i * A + cnt2 * to * C;
cnt2++; sig2 += B * to;
}
}
}
return ret;
}
inline int min(int x,int y,int z) {return min(min(x,y),z);}
inline int max(int x,int y,int z) {return max(max(x,y),z);}
inline ull calc3()
{
static int vis[N];
memset(vis,-1,sizeof(vis));
ull ret = 0;
for(int i = 0;i < n;i++)
{
for(auto to : G[i]) vis[to] = i;
for(auto to : G[i])
for(auto tw : G[to])
if(vis[tw] == i)
ret += min(i,to,tw) * A + (i + to + tw - min(i,to,tw) - max(i,to,tw)) * B + max(i,to,tw) * C;
}
return ret;
}
int main()
{
cin>>n>>m;
cin>>A>>B>>C;
for(int i = 1,x,y;i <= m;i++)
{
cin>>x>>y;
e[x].push_back(y); e[y].push_back(x);
deg[x]++; deg[y]++;
}
for(int i = 0;i < n;i++)
for(auto to : e[i])
if(lrg(to,i))
G[i].push_back(to);
cout<<calc0() - calc1() + calc2() - calc3();
return 0;
}