无向图,检测有无环,可以用并查集
#include<bits/stdc++.h> using namespace std; const int maxn=1e4; vector<pair<int,int> >a(maxn); int parent[maxn]; int rank_[maxn]; int n,m,x,y,k,v1,v2,op; void init(){ for(int i=0;i<maxn;i++)rank_[i]=0; for(int i=0;i<maxn;i++)parent[i]=i; } int find_(int x){ int x_root=x; while(parent[x_root]!=x_root){ x_root=parent[x_root]; } return x_root; } int union_point(int x,int y){ int x_root=find_(x); int y_root=find_(y); if(x_root!=y_root){ if(rank_[x_root]>rank_[y_root]){///以高度高的树作为根节点,高度不变 parent[y_root]=x_root; } else if(rank_[y_root]>rank_[x_root]){ parent[x_root]=y_root; } else {///只有在高度相等时,rank++ rank_[x_root]++; parent[x_root]=y_root; } return 1; } return 0;///同一个祖先,证明有环 } int main() { cin>>n; for(int i=0;i<n;i++){ cin>>v1>>v2; a[i]=make_pair(v1,v2); } init(); for(int i=0;i<n;i++){ if (union_point(a[i].first,a[i].second)==0){ cout<<"cycle detected!"<<endl; return 0; } } cout<<"no cycle found"<<endl; return 0; } /* 6 0 1 1 2 1 3 3 4 2 5 2 3 */
原文链接: https://www.cnblogs.com/mohari/p/12933799.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/350057
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!