再学一道算法题：部落（并查集）

部落
分数 25
作者 陈越
单位 浙江大学
在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。

输入格式：
输入在第一行给出一个正整数N（≤10
4
），是已知小圈子的个数。随后N行，每行按下列格式给出一个小圈子里的人：

K P[1] P[2] ⋯ P[K]

其中K是小圈子里的人数，P[i]（i=1,⋯,K）是小圈子里每个人的编号。这里所有人的编号从1开始连续编号，最大编号不会超过10 4 。

之后一行给出一个非负整数Q（≤10 4），是查询次数。随后Q行，每行给出一对被查询的人的编号。

输出格式：
首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询，如果他们属于同一个部落，则在一行中输出Y，否则输出N。

输入样例：
4
3 10 1 2
2 3 4
4 1 5 7 8
3 9 6 4
2
10 5
3 7
输出样例：
10 2
Y
N

#include<iostream>  
#include<cstring>  
#define maxn 100000  
int f[maxn];  
using namespace std;  
void init()       //初始化函数因为没有告知人数所以就到maxn(作用:根都为自己)  
{  
    for(int i=1;i<=maxn;i++){  
        f[i]=i;  
    }  
}  
int getf(int a)     //找爹函数(找根)  
{  
    if(f[a]==a) //找到根(爹是自己~ ~),退出  
        return a;  
    else{  
        f[a]=getf(f[a]);//递归调用，找该树的根(祖先)  
        return f[a];  
    }  
}  
void merge(int v,int u) //找两个树的关系，如果祖先不一样(即没有关系，就合并，这里采用偏左原则)  
{  
    int t1,t2;  
    t1=getf(v);  
    t2=getf(u);  
    if(t1!=t2){  
        f[t2]=t1;   //让t1为t2的爹  
    }  
}  
int main()  
{  
    int n1,party[maxn],map[maxn];  
    int m,n=0,su=0,n2;  
    int i,a,b;  
    int sum=0;  
    cin>>m;  
    init();  
    memset(map,-1,sizeof(maxn)); //把map的值都设为-1，函数头文件#include<csting>,格式:memset(地址，需要设置成的值，sizeof);   
    while(m--)  
    {  
        cin>>n1;  
        n=n+n1;  
        for(i=1;i<=n1;i++){  
            cin>>party[i];  
            map[party[i]]=1; //输入时会用重复的，用标记数组map，进行标记，把输入树对应的值改为1  
            if(i-1)  
                merge(party[i-1],party[i]);  
        }  
    }  
    for(i=0;i<=n;i++){   //n没实际含义，只是圈定了一个范围，毕竟maxn太大  
        if(map[i]==1){  
        sum++;  
        }  
    }  
   for(i=1;i<=sum;i++){  
    if(f[i]==i){  
    su++;  
    }  
   }  
   cin>>n2;  
   cout<<sum<<" "<<su<<endl;  
   while(n2--){  
       cin>>a>>b;  
       if(getf(a)==getf(b))  
        cout<<"Y"<<endl;  
       else  
        cout<<"N"<<endl; 
   }
   return 0;
}

写法二用set：

#include <iostream>
#include <set>
using namespace std;
int t, f[100001];
int find(int x)
{
    int num = x;
    while (num != f[num])
    {
        num = f[num];
    }
    while (x != f[x])
    {
        int z = x;
        x = f[x];
        f[z] = num;
    }
    return x;
}
int main()
{
    set<int> cun;
    for (int i = 0; i <= 10000; i++)
        f[i] = i;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        int num;
        cin >> num;
        cun.insert(num);
        n--;
        int x = f[num];
        while (n--)
        {
            cin >> num;
            cun.insert(num);
            f[find(num)] = x;
        }
    }
    set<int> cun1;
    int cou = 0;
    for (set<int>::iterator it = cun.begin(); it != cun.end(); it++)
        cun1.insert(find(*it));
    cou = cun1.size();
    cout << cun.size() << " " << cou << endl;
    cin >> t;
    while (t--)
    {
        int a, b;
        cin >> a >> b;
        if (find(a) == find(b))
        {
            cout << "Y" << endl;
        }
        else
        {
            cout << "N" << endl;
        }
    }
}