L2-024. 部落（并查集）

并查集，背模板就AC了，基本模板就是getf函数和merge函数，注意getf函数里面的que[k]=getf(que[k])，其中的que[k]=一定不能省略，这一步是压缩路径，如果少了这一步，非常容易运行超时！！！

#include<iostream>
#include<algorithm>
using namespace std;
int que[10005];
int getf(int k)
{
    return que[k]==k?k:que[k]=getf(que[k]);
}
/* int getf(int k)//运行超时 { return que[k]==k?k:getf(que[k]); } */ 
int merge(int a,int b)
{
    if (getf(a)!=getf(b))
    que[getf(a)]=getf(b); 
}
int main()
{
    int n,t,i,j,k,a,b,book[10005],count1=0,count2=0;
    fill(book,book+10005,0);
    for (i=0;i<10005;i++)
    que[i]=i;
    cin>>n;
    for (i=0;i<n;i++)
    {
        cin>>t;
        cin>>a;
        book[a]=1;
        for (j=1;j<t;j++)
        {
            cin>>b;
            book[b]=1;
            merge(a,b);
        }
    }
    for (i=0;i<10005;i++)
    {
        if (book[i]==1)
        {
            count1++;
            if (que[i]==i)
            count2++;
        }
    }
    cout<<count1<<" "<<count2<<endl;
    cin>>k;
    for (i=0;i<k;i++)
    {
        cin>>a>>b;
        if (getf(a)==getf(b))
        cout<<"Y"<<endl;
        else
        cout<<"N"<<endl;
    }
}