在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。
输入格式：
输入在第一行给出一个正整数N（≤104），是已知小圈子的个数。随后N行，每行按下列格式给出一个小圈子里的人：
K P[1] P[2] ⋯ P[K]
其中K是小圈子里的人数，P[i]（i=1,⋯,K）是小圈子里每个人的编号。这里所有人的编号从1开始连续编号，最大编号不会超过104。
之后一行给出一个非负整数Q（≤104），是查询次数。随后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
思路：
典型的并查集问题，先用pre[i]=x的形式，表示i的父节点为x;
之后两个函数,find(x)函数用来寻找x的祖先,join(x,y)函数用来把x和y的祖先设为共同的一个
int pre[10005]; int find(int x) { //如果x的父节点是他自己，那么他就是祖先 if(x==pre[x]) return x; //用来压缩路径,减少递归次数 return pre[x]=find(pre[x]); } void join(int x,int y) { //如果二者的祖先不相等,将其中一个的祖先的父节点设为另一个的祖先 int fx=find(x),fy=find(y); if(fx!=fy) { pre[fy]=fx; } }
之后再来看这道题，不停地join()就行。值得一提的小技巧是,对于每一个小圈子来说，取第一个编号来代表这个小圈子，整个小圈子的默认父节点都是它，存在一个数组里，最后遍历这个数组来统计人数以及部落个数。
代码如下：
#include <iostream> #include <unordered_set> using namespace std; typedef long long ll; ll pre[10005]; ll find(ll x) { if(x==pre[x]) return x; return pre[x]=find(pre[x]); } void join(ll x,ll y) { ll fx=find(x),fy=find(y); if(fx!=fy) { pre[fy]=fx; } } ll book[10005],cnt; int main() { unordered_set<ll> population,tribes; for(ll i=0;i<10005;i++) { pre[i]=i; } ll n; cin>>n; ll head[10005]={0}; for(ll x=0;x<n;x++) { ll k; scanf("%lld",&k); ll p[10005]={0}; for(ll i=0;i<k;i++) { scanf("%lld",&p[i]); population.insert(p[i]); join(p[0],p[i]); } head[x]=p[0]; } for(ll i=0;i<n;i++) { tribes.insert(find(head[i])); } printf("%d %d\n",population.size(),tribes.size()); ll q; cin>>q; while(q--) { ll a,b; scanf("%lld %lld",&a,&b); if(find(a)==find(b)) { cout<<"Y"<<endl; }else{ cout<<"N"<<endl; } } }
结果：
