博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
检查无向图的连通以及是否存在环
阅读量:5037 次
发布时间:2019-06-12

本文共 1142 字,大约阅读时间需要 3 分钟。

 

1 #include 
2 #include
3 #include
4 #include
5 using namespace std; 6 const int maxn=1e5+5; 7 8 int x; 9 int f[maxn];10 int find(int x){11 if(x!=f[x]){12 f[x]=find(f[x]);13 }14 return f[x];15 }16 void init(){17 for(int i=0;i<=100000;i++) 18 f[i]=i;19 }20 set
S;21 int main(){22 int a,b;int flag=1;23 std::ios::sync_with_stdio(false);24 init();25 while(cin>>a>>b){26 if(a==-1&&b==-1) break;27 if(a==0&&b==0)28 {29 //cout <<"flag="<
<
::iterator it=S.begin();41 if(!S.empty()) sign=find(*it),it++;42 for(;it!=S.end();it++){43 if(find(*it)!=sign) flag=0;44 //cout <<"in";45 }46 if(flag) cout <<"Yes\n";47 else cout <<"No\n";48 }49 //cout <<"in";50 flag=1;51 S.clear();52 init();53 }54 else55 {56 S.insert(a);S.insert(b); 57 int fa=find(a);58 int fb=find(b);59 //cout <<"root"<
<<" "<
<

 

因为分到了并查集专题,就直接想到用并查集。

如果要连的当前边的两个端点在之前的图中已经连通,那么当前边一定会与之前的图构成一个环,那么直接就不成立了。如果没有环,那么再判断是否连通,如果连通就成立。算是一道并查集的应用题。

转载于:https://www.cnblogs.com/Msmw/p/11262923.html

你可能感兴趣的文章
洛咕 P2480 [SDOI2010]古代猪文
查看>>
js-创建对象的几种方式
查看>>
JDK JRE Java虚拟机的关系
查看>>
2018.11.20
查看>>
word20161215
查看>>
12th week blog
查看>>
dijkstra (模板)
查看>>
python小记(3)
查看>>
编译Linux驱动程序 遇到的问题
查看>>
大型分布式网站架构技术总结
查看>>
HDU 1017[A Mathematical Curiosity]暴力,格式
查看>>
[算法之美] KMP算法的直观理解
查看>>
EntityFramework 性能优化
查看>>
Python学习-文件操作
查看>>
正则表达式()、[]、{}的区别
查看>>
第十二周作业
查看>>
Socket开发框架之框架设计及分析
查看>>
oracle.encode('gbk',errors='ignore').decode('gbk')
查看>>
kexec on openwrt - linux boots linux, kernel boots kernel on openwrt
查看>>
【练习赛2补题】zoj 2734 Exchange Cards 【DFS】
查看>>