题解 | #连通图#

#include<cstdio>
using namespace std;
#define N 1000
int father[N];//存储了父亲的下标
int high[N];//存储了某个根的树的高度
void Init(int n){
    //最开始每个元素单独构建一个集合,每个集合是一棵树
    for (int i = 1; i <= n; ++i) {
        //i的编号
        father[i]=i;//每个结点都是树的根
        high[i]=1;
    }

}
int find(int x){
    if (x!=father[x]){
        //find的路径压缩,找到祖先以后先不返回，而是设为自己的新父亲。
        father[x]= find(father[x]);
    }
    //x就是树的根
    return father[x];
}
void Union(int x, int y, int &num){
    //合并两棵树
//    father[find(y)] = father[x];

        x= find(x);
        y= find(y);
    if (x!=y){
        //x y原本不属于同一个连同子图
        --num;
    }
    if (high[x]<high[y]){
        father[x]=y;
    } else if (high[x]>high[y]){
        father[y]=x;
    } else{
        father[y] = x;
        ++high[x];
    }
}
int main(){
        int n;
        int m;
    while (scanf("%d%d",&n,&m)!=EOF){
        if (m==0&&n==0){
            break;
        }
        Init(n);
        int num=n;//连通子图的数量
        for (int i = 0; i < m; ++i) {
            int x,y;
            scanf("%d%d",&x,&y);
            Union(x,y,num);
        }
        if (num==1){
            printf("YES\n");
        } else{
            printf("NO\n");
        }
    }

}