部落

7-7 部落 （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 <bits/stdc++.h>
using namespace std;

#define Max 10005
int Tree[Max][2];

void setTree()
{
    for(int i=0;i<Max;i++)
    {
        Tree[i][0]=i;
        Tree[i][1]=-1;
    }
}

int findTree(int x)
{
    if(Tree[x][0]==x)return x;
    int temp=findTree(Tree[x][0]);
    Tree[x][0]=temp;
    return temp;
}

void union_set(int a,int b)
{
    int fa=findTree(a);
    int fb=findTree(b);
    if(fa!=fb)Tree[fa][0]=fb;
}

void cunzai(int j)
{
    Tree[j][1]=1;
}

int main()
{
    setTree();
    int Q;
    cin>>Q;
    for(int i=0;i<Q;i++)
    {
        int number;
        cin>>number;
        int first;
        cin>>first;
        cunzai(first);
        for(int k=0;k<number-1;k++)
        {
            int others;
            cin>>others;
            cunzai(others);
            union_set(first,others);
        }
    }
    for(int i=0;i<Max;i++)
    {
        findTree(i);
    }
    vector<int> QZ;
    int renshu=0;
    for(int i=0;i<Max;i++)
    {
        if(Tree[i][1]==1)
        {

            renshu++;
            int panduan=0;
            for(int w=0;w<QZ.size();w++)
            {
                if(Tree[i][0]==QZ[w])
                {
                    panduan=1;break;
                }
            }
            if(panduan==0)
                QZ.push_back(Tree[i][0]);
        }
    }
    cout<<renshu<<\" \"<<QZ.size()<<endl;

    int N;
    cin>>N;
    for(int i=0;i<N;i++)
    {
        int A,B;
        cin>>A>>B;
        if(findTree(A)!=findTree(B))
        {
            cout<<\"N\"<<endl;
        }
        else
        {
            cout<<\"Y\"<<endl;
        }
    }
    return 0;
}