连通图
连通图
http://www.nowcoder.com/questionTerminal/569e89823a5141fe8a11ab7d4da21edf
妈妈我终于学会并查集啦!
#include<stdio.h> int father[1005] = {0}; void init(int father[]) { for(int i = 0;i<1005;i++) father[i] = i; return; } int findfather(int n) { if(father[n] == n) return n; else return findfather(father[n]); } int main() { int n,m; int x,y; while(scanf("%d",&n) != EOF &&n) { scanf("%d",&m); init(father); for(int i = 0;i<m;i++) { scanf("%d%d",&x,&y); // 合并 int fx = findfather(x); int fy = findfather(y); if(fx != fy) father[fx] = fy; } int f = findfather(1); // 以1为起点 int flag = 1; for(int i = 1;i <= n;i++) // 判断是否连通 { if(findfather(i) != f) { flag = 0; break; } } if(flag) printf("YES\n"); else printf("NO\n"); } return 0; }