在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。
输入格式：
输入在第一行给出一个正整数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;
}
}
}
结果：
标签：pre,fx,15,--,ll,查集,int,小圈子,find From： https://www.cnblogs.com/daniel350-wang/p/17322250.html