描述
江湖上散落着各式各样的大侠，有上千个之多。他们没有什么正当职业，整天背着剑在外面走来走去，碰到和自己不是一路人的，就免不了要打一架。但大侠们有一个优点就是讲义气，绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”，只要是能通过朋友关系串联起来的，不管拐了多少个弯，都认为是自己人。这样一来，江湖上就形成了一个一个的帮派，通过两两之间的朋友关系串联起来。而不在同一个帮派的人，无论如何都无法通过朋友关系连起来，于是就可以放心往死了打。但是两个原本互不相识的人，如何判断是否属于一个朋友圈呢？
我们对n个人用1~n编号，用a[i]存储i的“大哥”，如果一个人没有“大哥”，则a[i]=i（即大哥就是自己）。如n=5：
| 下标 | 1 | 2 | 3 | 4 | 5 |
| 值 | 3 | 4 | 5 | 4 | 5 |
说明：“1”号的大哥是“3”号，“3”号的大哥是“5”号，“5”号的大哥是自己，因此"5"号是“1”号和“3”号的老大，这三个人构成一个朋友圈。
现在给出n个人的若干个朋友圈，有m次询问，每次询问u和v是不是在同一个朋友圈里。
输入
第一行为正整数n和m（1<=n, m<=1000），表示有n个侠士（1~n编号），m次查询。
第二行有n个数a[i]，a[i]表示是编号为“i”的大哥，在1~n之间。
接下来有m行，每行两个正整数u和v，(1<=u, v<=n, u≠v)，表示待查询的两个侠士编号。
数据保证，每个人都最多只认一个大哥。
输出
对每次查询，如果在同一个朋友圈输出Yes，否则输出No
样例输入
5 3
3 4 5 4 5
1 3
4 2
1 4
样例输出
Yes
Yes
No
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10,inf = 0x3f3f3f3f,M = 2*1e4+10;
int f[N],a[N],maxn,x[M],y[M];
int n,ans,m;
int find(int x) //找到x的祖先
{
if(f[x]!=x)f[x] = find(f[x]); //如果x的爹不是自己，那么去寻找爹中爹
return f[x];
}
void merger(int x,int y) //合并x和y两个集合
{
int fx = find(x);
int fy = find(y);
if(a[fx]<a[fy])swap(fx,fy); //交换位置，保证fx所在的关系网人数是比较多的
a[fx] = a[fx] + a[fy];
ans = max(ans,a[fx]);
f[fy] = fx; //fy的祖先是fx
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>f[i];
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
if(find(x)==find(y))cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
标签：7922,int,江湖,查集,朋友,大哥,朋友圈,find From： https://www.cnblogs.com/jyssh/p/17364912.html