无向图三元环计数
O(msqrt(m))O(m sqrt(m))O(msqrt(m))
ll solve(ll n,ll m)
{
ll a,b;
FOR(i,1,n)
{
RLL2(a,b);e.pb(P(a,b));
++d[a],++d[b];
}
FOR(i,1,m)
{
ll u = e[i].first,v = e[i].second;
if(d[u] < d[v] || (d[u] == d[v] && u > v)) swap(u,v);
G[u].pb(v);
}
ll ans = 0;
FOR(i,1,n)
{
for(auto u:G[i]) vis[u] = i;
for(auto u:G[i]) for(auto v:G[u]) if(vis[v] == i) ans++;
}
return ans;
}
有向图三元环计数
先将图转化为无向图，然后用无向图方法求出三元环，因为数量不超过O(msqrt(m))O(m sqrt(m))O(msqrt(m))
所以可以求出来以后在在原图上判断该三元环是否存在
竞赛图三元环计数
先考虑所有方案数，任选三点的方案数为Cn3C_n^3Cn3
然后去掉不合法的，对于一个点iii，不可能存在一个三元环，不可能存在两条出边来至该点
因此对于该点的方案数为 C∣d[i]∣2C_{|d[i]|}^2C∣d[i]∣2
所以总方案数为
Cn3−∑inC∣d[i]∣2C_n^3 - \sum_i^n C_{|d[i]|}^2
Cn3−i∑nC∣d[i]∣2
Read More ~
