题解 | #连通图#

#define N 2000
#include<cstdio>
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) {
    if (x != father[x]) {
        father[x] = Find(father[x]);
    }
    return father[x];
}
void Union(int x, int y, int& num) {
    x = Find(x);
    y = Find(y);
    if (x != y) { //原本不属于同一个联通子图
        --num;
    }
    if (height[x] < height[y]) {
        father[x] = y ;
    } else if (height[x] > height[y]) {
        father[y] = x;
    } else {
        father[x] = y ;
        ++height[y];
    }
}
int main() {
    int n, 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");
            }
    }
}