在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。
输入格式：
输入在第一行给出一个正整数N（≤104），是已知小圈子的个数。随后N行，每行按下列格式给出一个小圈子里的人：
K P[1] P[2] ⋯ P[K]
其中K是小圈子里的人数，P[i]（i=1,⋯,K）是小圈子里每个人的编号。这里所有人的编号从1开始连续编号，最大编号不会超过104。
之后一行给出一个非负整数Q（≤104），是查询次数。随后Q行，每行给出一对被查询的人的编号。
输出格式：
首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询，如果他们属于同一个部落，则在一行中输出Y，否则输出N。
输入样例：
1. 4 2. 3 10 1 2 3. 2 3 4 4. 4 1 5 7 8 5. 3 9 6 4 6. 2 7. 10 5 8. 3 7
思路：因为每个人可能在多个圈子里面，所以使用set对每个成员的编号进行去重，用并查集把同一个人所在的不同圈子合并成一个部落，然后遍历一下set求出合并之后有多少部落，最后使用并查集判断一下是否属于同一个部落
输出样例：
1. 10 2 2. Y 3. N
#include<iostream> #include<set> using namespace std; const int N=1e4+10; int p[N]; int find(int x) { if(x!=p[x]) p[x]=find(p[x]); return p[x]; } int main() { int n; set<int>s;//可以对出现相同的人去重 for(int i=0;i<N;i++) p[i]=i; cin>>n; while(n--) { int k,x,y; cin>>k>>x;//先输入一个数方便合并集合 s.insert(x); k--; while(k--) { cin>>y; s.insert(y); p[find(x)]=y; } } int cnt=0; for(auto x:s) if(find(x)==x) cnt++;//集合的数量 cout<<s.size()<<' '<<cnt<<endl; int k,x,y; cin>>k; while(k--) { cin>>x>>y; if(find(x)==find(y)) puts("Y"); else puts("N"); } return 0; }
