题解 | 连通图

#include <bits/stdc++.h>
using namespace std;

const int MAXN=1000;

int father[MAXN];
int height[MAXN];

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

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(x!=y){
        if(height[x]<height[y])father[x]=y;
        else if(height[y]<height[x]) father[y]=x;
        else {
            father[y]=x;
            height[x]++;
        }
    }
}

int main(){
    int n,m;
    while(cin>>n>>m){
        if(n==0)break;
        init(n);
        while(m--){
            int x,y;
            cin>>x>>y;
            Union(x,y);
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            if(Find(i)==i)ans++;
        }
        if(ans==1)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}

#大学最后一个寒假，我想……#这个问题的解决思路和上一个题解一样。

寒假考研党一起努力成功上岸吧