【精讲】图论算法——并查集入门

某个家族人员过于庞大,

要判断两个人是否是亲戚很不容易。

现在给出某个亲戚关系图,

求任意给出的两个人是否具有亲戚关系。

这是亲戚的题面


我们先不要管这道题的输入输出,

我们假设他给出的不是两个人的亲戚关系,

而是告诉你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(克鲁斯卡尔)算法就是用并查集实现判断回路的。

如果评论区有人让我讲的话,

我以后可能会去把这个克鲁斯卡尔算法讲一下。


那么今天就讲到这里,如有不对请指正!

上一篇:P3412 仓鼠找sugar II 题解


下一篇:2021.10.16CSP模拟赛22 赛后总结