题解 | #连通图#

#include <iostream>
#include <fstream>
using namespace std;

const int MAXN=1000;
class UF
{
private:
    int _n;
    int _rank[MAXN];
    int _uf[MAXN];
protected:
    virtual void initialize(int n);
public:
    UF(int n):_n(n){initialize(n);}
    int mfind(int x);
    int getN();
    void mmerge(int x,int y);
};

int main()
{
    //ifstream fin("C:\\Users\\Administrator\\Desktop\\Code\\c2006c\\fin.txt");
    //ofstream fout("C:\\Users\\Administrator\\Desktop\\Code\\c2006c\\fout.txt");
    int n,m,x,y;
    while(cin>>n>>m)
    {
        if(n==0) break;
        UF uf(n);
        while(0<m--)
        {
            cin>>x>>y;
            uf.mmerge(x-1,y-1);
        }
        if(uf.getN()==1)
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }

    }



    return 0;
}


void UF::initialize(int n)
{
    for(int i=0;i<n;++i)
    {
        _rank[i]=1;
        _uf[i]=i;
    }
}
int UF::mfind(int x)
{
    if(_uf[x]==x)
        return x;
    return _uf[x]=mfind(_uf[x]);
}
int UF::getN()
{
    return _n;
}
void UF::mmerge(int x,int y)
{
    int tx=mfind(x);
    int ty=mfind(y);
    if(tx==ty) return;
    --_n;
    if(_rank[tx]<=_rank[ty])
    {
        _uf[tx]=ty;
    }
    else
    {
        _uf[ty]=tx;
    }
    if(_rank[tx]==_rank[ty])
    {
        ++_rank[ty];
    }



}