首页 > 代码库 > 无向图求三元环

无向图求三元环

2024-09-16 05:58:47   218人阅读

http://acm.xidian.edu.cn/problem.php?id=1187

问题重述:给一个无向图，求其中包含 3 个结点的环的个数。

题解 暴力玄学，枚举边然后双指针扫描两个端点的邻集。注意用结点的顺序 关系去重，最后除以 3 会超时的。时间复杂度应该是 O(nm)，不知道怎么过的。 网上 O(m√m) 的反而过不了。 

注意如何避免除以三的遍历方式。

 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdlib> 5 #include<vector> 6 using namespace std; 7 typedef long long ll; 8 vector<int>G[100001]; 9 int u[100001],v[100001];10 int main(){11     int T;12     scanf("%d",&T);13     while(T--){14         int n,m;15         scanf("%d%d",&n,&m);16         for(int i=1;i<=n;i++){17             G[i].clear();18         }19         20         for(int i=1;i<=m;i++){21             scanf("%d%d",u+i,v+i);22             if(u[i]>v[i]){23                 swap(u[i],v[i]);24             }25             G[u[i]].push_back(v[i]);26         }//小点指向大点27         28         for(int i=1;i<=n;i++) sort(G[i].begin(),G[i].end());29         30         ll ans=0;31         32         for(int i=1;i<=m;i++){33             vector<int>::iterator iu=G[u[i]].begin(),iv=G[v[i]].begin();34             35             for(;iu!=G[u[i]].end();iu++){36                 while(iv!=G[v[i]].end() && *iv<*iu) iv++;37                 if(iv==G[v[i]].end()) break;38                 if(*iv==*iu) ans++;39             }40         }41         printf("%lld\n",ans);42     }43     return 0;44 }

 

无向图求三元环


联系
我们