题解 | 连通图

#include<stdio.h>

struct Point{
    int x;
    int y;
};
struct Edge{
    int from;
    int to;
    int height;
};

struct Point point[1000];
struct Edge edge[1000*999/2];
int father[1001];
int height[1001];

void inital(int n){
    for(int i = 1; i <= n; i++){
        father[i] = i;
        height[i] = 1;
    }
}

int Find(int x){
    if(father[x] != x){
        father[x] = Find(father[x]);
    }
    return father[x];
}

void Union(int a, int b){
    a = Find(a);
    b = Find(b);
    if (a != b){
        if(height[a] > height[b]){
            father[b] = a;
        }
        else if (height[a] < height[b])
        {
            father[a] = b;
        }
        else{
            father[a] = b;
            height[b]++;
        }
        
    }
}

int main(){
    int n, m;
    int a, b;
    int x, y, c = 0;

    while(scanf("%d %d", &n,&m) != EOF){
        c = 0;
        if (n == 0 || m == 0) break;
        inital(n);
        for(int i = 0; i < m; i++){
            scanf("%d %d", &a, &b);
            Union(a, b);
        }
        x = Find(1);
        for(int i = 2; i <= n;i++){
            y = Find(i);
            if (x == y) continue;
            else{
                c++;
                x = y;
            }
            
        }
        if(c != 0) printf("%s\n","NO");
        else printf("%s\n", "YES");
        //printf("%d\n", c);
    }
   return 0;
}