某个家族人员过于庞大，
要判断两个人是否是亲戚很不容易。
现在给出某个亲戚关系图，
求任意给出的两个人是否具有亲戚关系。
这是亲戚的题面
我们先不要管这道题的输入输出，
我们假设他给出的不是两个人的亲戚关系，
而是告诉你a是b的儿子。
那我这个时候就出现了二条
基本的法则：
1.如果a是b的儿子，那么b就不是a的儿子。
2.一个人可以有多个儿子，但只能有一个父亲。
这个时候我们再来思考，
什么情况下两人构成亲戚关系呢？
他们可能是兄弟关系，也就是有共同的父亲，
有可能是父子关系，也就是一方是另一方的父亲，
有可能是叔侄关系……
关系有很多，但其实只有一条——
亲戚的亲戚就是亲戚，
跟自己亲戚不是亲戚的就不是亲戚。
根据这条，我们可以将一个家族谱简单处理。
由此发现，无论如何，
每个小家庭都构成一个树，
而整个大家庭就是一片森林。
因此亲戚其实就是
判断他是否在同一个树。
只需要记录下来他们的父亲，
不断递归，来判断树根是否一致，
树根就是自己是自己的父亲。
代码如下：
int find(int x)
{
if(x!=fa[x])//如果不是树根
{
return find(fa[x]);//返回父亲的父亲
}
return fa[x];//不然返回树根
}
这样子看起来很完美,
事实上问题也很明显，
那就是当数据足够大的时候。
递归会显得很吃力。
其实我们求的是树根，
但是我们却每一次都要不断的递归,
如果父亲数组直接记录树根，那就可以节省很多时间。
我们每一次去找父亲的父亲时，
返回来的是树根，
这个时候我们把父亲设为这个树根，
等到下一次再搜的时候可以直接返回树根。
当然这个方法也有问题——大逆不道！
前一秒你的父亲还是你的父亲，
后一秒他就跟你是兄弟了。
当然，你父亲的父亲也成了你的兄弟……
但我们才管他是不是大孝子，我们能AC就行，
由此打出优化
int find(int x)
{
if(x!=fa[x])//如果不是树根
{
fa[x]=find(fa[x]);//把父亲设为父亲的父亲
}
return fa[x];//返回树根
}
现在我们重新看回题面，
打出这个题目的代码。
#include<bits/stdc++.h>
using namespace std;
int fa[100001];
int find(int x)
{
int son=x;
if(x!=fa[x])
{
fa[x]=find(fa[x]);
}
return fa[x];
}
void join(int a,int b)//合并的代码,仅供参考。
{
int x=find(a);
int y=find(b);
if(x!=y)fa[x]=fa[y];//注意是设为别人的父亲,这是一个优化。
return;
}
bool pd(int a,int b)
{
int x=find(a);
int y=find(b);
if(x!=y)return false;
else return true;
}
int main()
{
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i=1; i<=n; i++)fa[i]=i;
for(int i=1; i<=m; i++)
{
int x,y;
scanf("%d%d",&x,&y);
join(x,y);
}
scanf("",);
for(int i=1; i<=k; i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(pd(x,y)) printf("Yes\n");
else printf("No\n");
}
return 0;
}
这个算法就是并查集算法，
并代表合并，
查代表查询，
集代表集合。
也就是可以合并和查询的一个集合。
并查集虽然是一种图论算法，但其实只要学了递归就可以学。
那么他为什么是一种图论算法呢？
因为它可以判断回路,
同时还存在带权并查集这种玩法,
最小生成树经典算法——
Kruskal(克鲁斯卡尔)算法就是用并查集实现判断回路的。
如果评论区有人让我讲的话，
我以后可能会去把这个克鲁斯卡尔算法讲一下。
那么今天就讲到这里,如有不对请指正!