kuangbin带你飞并查集专题总结

最近花了一段时间做了kuangbin带你飞并查集专题，今天来做个总结！！！

并查集本来以为很简单的，做了专题才发现，以前的自己真天真。

并查集，顾名思义：用来快速实现合并，查询集合的操作（缺点：对于把元素提出集合的操作实现不了）

关于最简单的并查集操作和过程，这里也不多说了，大家可以看啊哈算法里面的讲解，既生动又形象。

这里强推几个好的讲解：

【坐在马桶上看算法】啊哈算法13：零基础彻底弄懂"并查集"

超有爱的并查集~

这都精心挑选的博客，也可以看刘汝佳紫书中在Kruskal算法中讲的并查集，精（nan）简（dong）或者blibili上的资源（真心强大

并查集就有两个操作：合并和查询，对应两种优化，按秩合并和路径压缩。

这里先讲查询（上代码）：

两种实现方法：递归和循环（更快点，适合数据范围比较大的题）

一：递归（很短很短！！！！）

int find(int x){
        if(p[x]==x) return x;//根节点
        return p[x]=find(p[x]);//路径压缩
	//return p[x]==x?x:p[x]=find(p[x]);
}

二：循环

int p[1010]; //存放第i个元素的父节点
int unionsearch(int x) //查找根结点
{
	int son, tmp;
	son = x;
	while(x != p[x]) //寻找根结点
		x = p[x];
	while(son != x) //路径压缩
	{
		tmp = p[son];
		p[son] = x;
		son = tmp;
	}
	return p[x];
}

合并操作要根据题目要求进行合并，同理查询也是如此。

下面给出基于按秩合并的优化的代码

void UNION(int x, int y) {
	int f1 = find(x);
	int f2 = find(y)；
	if (rank[f1] <= rank[f2]) {
		root[f1] = f2;
		if (rank[f1] == rank[f2]) {
			rank[f2] ++; 	
		}	
	} 
        else {
		root[f2] = f1;
	}
};

下面给出几道kuangbin带你飞并查集基础题：

下面来点有意思(nan)的，带权并查集，普通的并查集只有节点之间的关系（与根节点的边没有权值），而没有其他具体的信息。

这里我们给节点到根节点之间的边附上有一定意义的权值，就变成了带权并查集。

因此我们在查询和合并时的代码就要根据题目进行改动。

总的来说，大都是开几个数组，用来表示当前节点到根节点的值，然后在查询和合并时修改值。

在修改时按照向量的方法进行，这类题还是要自己画图理解一下，不然遇到题还是不会。

不懂可以参考这两篇文章：

带权并查集

深入理解带权并查集（例题+思考）

下面将一下并查集的经典应用。

并查集是判断图是否存在环的一种快捷方法，也是判断图是不是一棵树的便捷方法。

看这两道题应该就能懂了，也算是并查集的一种灵活应用。