题解 | #连通图#

//采用并查集解决
#include "stdio.h"
#define N 1000
using namespace std;
int father[N];
int height[N];
void init(int n){//并查集的初始化操作
    for (int i = 1; i <= n; ++i) {
        father[i] = i;
        height[i] = 1;
    }
}

int find(int x){//带有压缩路径的并查集查找操作,查找x的父亲
    if(x != father[x]){
        father[x] = find(father[x]);
    }
    return father[x];
}

void Union(int x,int y){
    x = find(x);//找到x的祖先根结点
    y = find(y);//找到y的祖先根节点
    if(height[x] > height[y]){
        father[y] = x;
    } else if(height[x] < height[y]){
        father[x] = y;
    } else{
        father[x] = y;
        ++height[y];
    }
}

int main(){
    int n,m;//n为顶点数目，m为边的数目
    while (scanf("%d%d",&n,&m)!=EOF){
        if(m == 0 && n == 0)
            break;
        init(n);
        int x,y;int sum = 0;//sum统计并查集节点的个数
        for (int i = 0; i < m; ++i) {
            scanf("%d%d",&x,&y);
            int x_father = find(x);
            int y_father = find(y);
            if(x_father == y_father){
                continue;
            } else{
                Union(x,y);
                ++sum;
            }
        }
        if(sum == n-1)
            printf("YES\n");
        else
            printf("NO\n");
    }
}