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

本文主要是介绍【精讲】图论算法——并查集入门，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

某个家族人员过于庞大，

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

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

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

这是亲戚的题面

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

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

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

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

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

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

这篇关于【精讲】图论算法——并查集入门的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！