算法分享———并查集巧解图的连通性问题
算法分享———并查集巧解图的连通性问题
并查集（Union-Find Set）是一种用于处理图的连通性问题的重要数据结构。它通过维护每个节点的“父亲”关系，高效地实现了判断两个节点是否连通、合并两个连通分量等操作。本文将从并查集的基本概念出发，详细讲解其核心思想、实现方法，并通过具体代码示例展示其在实际问题中的应用。
什么是并查集？
并查集是一种图形数据结构，用于存储图中结点的连通关系。
并查集的基本思想
每个结点有一个父亲，可以理解为“一只伸出去的手”，会指向另外一个点，初始的点指向自己，一个点的根节点是该点的父亲的父亲的父亲的.......直到某个点的父亲是自己（根），所以也可以理解为寻祖算法，当两个点的根相同时，我们就说他们是同一类，或者说是连通的。
并差集该怎么实现？
根据上面的分析，我们不难想到递归的算法
找根的方法：如果当前点不是根，就返回父亲的根，否则就是自己。
int root(int x)
{
if(pre[x]==x)return x;//结点的父亲就是自己说明该点就是根直接返回
return root(pre[x]);//否则递归调用寻找父亲的父亲
}
如图所示，7找根时会去找5的根，5找根时会去找1的根，1会去找3的根，3找根时发现指向自己即自己就是根所以直接返回3，3就是根，同理4找2，2指向自己，即2就是根，最后发现4的根是2，7的根是3，根不同说明4和7不连通，这就是并查集的原理，通过判断根是否相同来判断图是否连通，读者可深入体会。
并查集该如何合并根？
在并查集中，所有的操作都在根上，假如我要使得x和y两个点合并，只需要将root（x）指向root（y）,或使得root(y)指向root（x）..
即pre[root(x)]=root(y);或pre[root(y)]=root(x)我们来看一个例子
我们要把4和6合并只需要操作他们的根即可，即让2指向3（把指向自己的箭头取消）或3指向2，即以2做根或以3做根，这样就可以实现合并操作了。
并查集如何实现路径压缩？
根据上面的分析我们可以得出在最坏的情况下查找根的时间复杂度会达到O（n）,我们可以在找根的过程中，将父亲直接指向根，从而实现路径压缩，这样可以使得找根的总体时间复杂度接近O（1），如下图，执行一次root（7）之后，沿途的点都会直接指向根3。
int root(int x)
{
return pre[x]=(pre[x]==x?x:root(pre[x]));
}
这样边找边换根可以降低查找路径的时间复杂度。
实战应用
这是一道典型的并查集模型，红绳就是连通的意思，朋友之间的关系可以用并查集维护。
代码实现
运行结果
通过上面的例子我们可以总结出并查集的关键步骤如下：
- 路径压缩函数
- 初始化操作
- 合并操作
- 判断连通操作（判断根是否相同）
上述4步是并查集问题的模板，读者可以利用模板去尝试解决其他相似问题。