Happy Birthday！LevOJ P1790 小胡同学的连通图

思路:

用并查集判断有几个联通分量，联通分量个数>1，则说明不是连通图。

AC代码：

#include<bits/stdc++.h>

using namespace std;

const int N=505;

int n,m;
int fa[N];
int cnt;

int Find(int x){
    if(fa[x]==-1){
        return x;
    }else{
        return fa[x]=Find(fa[x]);
    }
}

void Union(int x,int y){
    x=Find(x);
    y=Find(y);
    if(x!=y){
        fa[x]=y;    
    }
}


int main(){
    cin>>n>>m;
    memset(fa,-1,sizeof(fa));
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        Union(x,y);
    }
    
    for(int i=1;i<=n;i++){
        if(Find(i)==i){
            cnt++;
        }
    }
    if(cnt>1){
        cout<<"No"<<endl;
    }else{
        cout<<"Yes"<<endl;
    }
    return 0;
}