无向图三元环计数
三元环
无向图 \(G\) 的三元环指的是一个 \(G\) 的一个子图 \(G_0\)，满足 \(G_0\) 有且仅有三个点 \(u\)，\(v\)，\(w\)，有且仅有三条边 \((u, v)\)，\((v, w)\)，\((w, u)\)。两个三元环 \(G_1, G_2\) 不同当且仅当存在一个点 \(u\)，满足 \(u \in G_1\) 且 \(u \notin G_2\)。
solution
考虑给边一个方向，重新建图，规则如下：
- 如果一条边两个端点的度数不一样，则由度数较小的点连向度数较大的点
（ps：大向小连边好像也可过，但是复杂度不会证） - 如果度数一样，则由编号较小的点连向编号较大的点（或其他规则）
可以证明新建的图是有向无环图（DAG）
原图中的三元环一定与对应有向图中所有形如 \((u→v)\)，\((u→w)\)，\((v→w)\) 的子图一一对应
只需要枚举 \(u\) 的出边，再枚举 \(v\) 的出边，然后检查 \(w\) 是不是 \(u\) 指向的点即可
复杂度证明
- 当\(deg[u]\le\sqrt{m}\)时，由于新图中\(u\)的出度不大于原图中\(u\)的度数，所以\(u\)的出度是\(O(\sqrt{m})\)的
- 当\(deg[u]>\sqrt{m}\)时，由于它只能向原图中度数大于等于它的点连边，又因为原图中所有的点的度数和是\(O(m)\)的，所以原图中度数大于\(\sqrt{m}\)的点是\(O(\sqrt{m})\)的，所以\(u\)的出度是\(O(\sqrt{m})\)的
il int calc(){
ri int as=0;
for(ri int i=1;i<=m;++i){
if(deg[u[i]]<deg[v[i]]) e[u[i]].push_back(v[i]);
else if(deg[u[i]]>deg[v[i]]) e[v[i]].push_back(u[i]);
else{
if(u[i]<v[i]) e[u[i]].push_back(v[i]);
else e[v[i]].push_back(u[i]);
}
}
for(ri int i=1;i<=n;++i){
for(ri int vi:e[i]) t[vi]=i;
for(ri int vi:e[i]){
for(ri int w:e[vi]){
if(t[w]==i) as++;
}
}
}
return as;
}
AC·code
#include<bits/stdc++.h>
#define il inline
#define ri register
#define cs const
using namespace std;
namespace Q{
il int rd(){
ri int x=0;ri bool f=0;ri char c=getchar();
while(!isdigit(c)) f|=(c==45),c=getchar();
while(isdigit(c)) x=x*10+(c^48),c=getchar();
return f?-x:x;
}
il void wt(int x){
if(x<0) x=-x,putchar(45);
if(x>=10) wt(x/10);
return putchar(x%10+48),void();
}
} using namespace Q;
cs int N=1e5+1,M=2e5+1;
int n,m,u[M],v[M],deg[N],t[N];
vector<int> e[N];
il int calc(){
ri int as=0;
for(ri int i=1;i<=m;++i){
if(deg[u[i]]<deg[v[i]]) e[u[i]].push_back(v[i]);
else if(deg[u[i]]>deg[v[i]]) e[v[i]].push_back(u[i]);
else{
if(u[i]<v[i]) e[u[i]].push_back(v[i]);
else e[v[i]].push_back(u[i]);
}
}
for(ri int i=1;i<=n;++i){
for(ri int vi:e[i]) t[vi]=i;
for(ri int vi:e[i]){
for(ri int w:e[vi]){
if(t[w]==i) as++;
}
}
}
return as;
}
signed main(){
n=rd(),m=rd();
for(ri int i=1;i<=m;++i){
u[i]=rd(),v[i]=rd();
deg[u[i]]++,deg[v[i]]++;
}
wt(calc());
return 0;
}
也可以枚举边 \((u→v)\) ，判断是否存在点 \(w\)，满足同时存在边 \((u→w)\)，\((v→w)\)（ps：但是慢很多）
il int calc(){
ri int s=0;
for(ri int i=1,u,v;i<=m;++i){
u=o[i].u,v=o[i].v;
if(deg[u]<deg[v]) e[u].push_back(v);
else if(deg[u]>deg[v]) e[v].push_back(u);
else{
if(u<v) e[u].push_back(v);
else e[v].push_back(u);
}
}
for(ri int i=1,u,v;i<=m;++i){
u=o[i].u,v=o[i].v;
for(ri int q:e[u]) vs[q]=i;
for(ri int q:e[v]) if(vs[q]==i) s++;
}
return s;
}
AC·code
#include<bits/stdc++.h>
#define il inline
#define cs const
#define ri register
#define int long long
using namespace std;
namespace Q{
il int rd(){
ri int x=0;ri bool f=0;ri char c=getchar();
while(!isdigit(c)) f|=(c==45),c=getchar();
while(isdigit(c)) x=x*10+(c^48),c=getchar();
return f?-x:x;
}
il void wt(int x){
if(x<0) x=-x,putchar(45);
if(x>=10) wt(x/10);
return putchar(x%10+48),void();
}
} using namespace Q;
cs int N=1e5+1;
int n,m,as,deg[N],vs[N];
struct qwq{
int u,v;
}o[N<<1];
vector<int> e[N];
il int calc(){
ri int s=0;
for(ri int i=1,u,v;i<=m;++i){
u=o[i].u,v=o[i].v;
if(deg[u]<deg[v]) e[u].push_back(v);
else if(deg[u]>deg[v]) e[v].push_back(u);
else{
if(u<v) e[u].push_back(v);
else e[v].push_back(u);
}
}
for(ri int i=1,u,v;i<=m;++i){
u=o[i].u,v=o[i].v;
for(ri int q:e[u]) vs[q]=i;
for(ri int q:e[v]) if(vs[q]==i) s++;
}
return s;
}
signed main(){
n=rd(),m=rd();
for(ri int i=1;i<=m;++i){
o[i]={rd(),rd()};
deg[o[i].u]++,deg[o[i].v]++;
}
wt(calc());
return 0;
}
原文链接: https://www.cnblogs.com/windymoon/p/17086675.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/315732
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
