并查集 POJ 1611

简单并查集，

时间复杂度

O(n*α(n))其中α(x)，对于x=宇宙中原子数之和，α(x)不大于4。事实上，路经压缩后的并查集的复杂度是一个很小的常数。

//484K    47MS


#include <iostream>
using namespace std;
int M,N;
const int MAX=30001;
int P[MAX];
int R[MAX];

int Find(int id)//查找 递归路径压缩

{
    if(P[id]!=id)
        P[id]=Find(P[id]);
    return P[id];
}
void Union(int x,int y)//合并
{
    int r1=Find(x);
    int r2=Find(y);
    if(r1==r2)
        return;
    if(R[r1]>R[r2])
        P[r2]=r1;
    else
    {
        P[r1]=r2;
        if(R[r1]==R[r2])
            ++R[r2];
    }
}

int main()
{
    while(cin>>M>>N&&(M||N))
    {
        for(int i=0;i<MAX;i++)
        {
            P[i]=i;
            R[i]=0;
        }
        for(int i=0;i<N;i++)
        {
            int K,t,f;
            cin>>K;
            if(K>=1)
                cin>>f;
            for(int l=1;l<K;l++)
            {
                cin>>t;
                Union(f,t);
            }
        }
        int sum=1;
        //cout<
        for(int i=1;i<M;i++)
        {
            if(Find(i)==Find(0))
                sum++;
        }
        cout<<sum<<endl;
    }
    return 0;
}