题解 | #连通图#

#include<iostream>
using namespace std;
const int maxn=1010;
int Father[maxn];
int height[maxn];

void Initial(int n){
    for(int i=0;i<=n;i++){
        Father[i]=i;
        height[i]=1;
    }
    return ;
}
int Find(int x){//路径压缩查找
    if(x!=Father[x]){
        Father[x]=Find(Father[x]);
    }
    return Father[x];
}

void Union(int x,int y){//低树合并到高树
    x=Find(x);
    y=Find(y);
    if(height[x]>height[y]){
        Father[y]=x;
    }
    else if(height[x]<height[y]){
        Father[x]=y;
    }
    else {
        Father[x]=y;
        height[y]++;
    }
    return;
}
 int main(){
     int  n,m;
     while(scanf("%d",&n)!=EOF){
         if(n==0)break;
         scanf("%d",&m);
         Initial(n);
         int x,y;
         for(int i=0;i<m;i++){
             scanf("%d%d",&x,&y);
             Union(x,y);
         }
         int ans=0;
         for(int i=1;i<=n;i++){
             if(Find(i)==i)ans++;//查找连通分量
         }
         if(ans==1)printf("YES\n");
         else printf("NO\n");
     }
     return 0;
 }