分析:题目大致意思等同于，给定几个点和几条边，问从某点开始能否遍历所有点，并且这个图中没有环。该题可以使用并查集来做。在进行合并时，合并的集合cnt++，表示当前合并的集合总数。另外要注意判断是否有环的问题，当进行合并的时候，如果两个节点拥有相同的祖先，则再加一条边就会形成环。
#include <iostream> using namespace std; int f[1010]; int cnt=0; int findFather(int x) { int a=x; while(x!=f[x]) { x=f[x]; } while(a!=f[a]) { int z=a; a=f[a]; f[z]=x; } return x; } int flag_false=0; bool unionf(int a,int b) { int fa=findFather(a); int fb=findFather(b); if(fa!=fb) { cnt++; f[fa]=fb; return true; } else { flag_false=1; return false; } } int main() { int m,n; while(cin>>n>>m) { if(m==0&&n==0) break; for(int i=1;i<1010;i++) { f[i]=i; } int a,b; cnt=1; flag_false=0; for(int i=0;i<m;i++) { cin>>a>>b; unionf(a,b); } if(cnt==n&&flag_false==0) { cout<<"Yes"<<endl; } else { cout<<"No"<<endl; } } }
原文：http://www.cnblogs.com/xiongmao-cpp/p/6433380.html