EOJ 1816. 连通

本文主要是介绍EOJ 1816. 连通，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.ecnu.edu.cn/problem/1816/

思路：并查集

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define INF 110
int set[1000005];int find(int x){return x==set[x]?x:(set[x]=find(set[x]));   //递归查找集合的代表元素，含路径压缩。
}int main()
{int n,m,i,x,y;scanf("%d%d",&n,&m);for(i=1;i<1000005;++i)     set[i]=i;for(i=0;i<m;++i){int a,b;scanf("%d%d",&a,&b);int fx=find(a),fy=find(b);set[fx]=fy;                      //合并有边相连的各个连通分量}int cnt=0;for(i=1;i<=n;++i)          //统计集合个数，即为连通分量个数，为一时，图联通。if(set[i]==i)++cnt;if(cnt==1)printf("yes\n");elseprintf("no\n");return 0;
}

这篇关于EOJ 1816. 连通的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---