【算法与数据结构】并查集详解

一，什么是并查集

二，并查集的结构

三，并查集的代码实现

1，并查集的大致结构和初始化

2，find操作

3，Union操作

4，优化

小结：

四，并查集的应用场景

省份数量[OJ题]

一，什么是并查集

核心概念：并查集是一种用于管理元素分组的数据结构。

在一些应用问题中，需将n个不同的元素划分成一些不相交的集合，开始时，n个元素各自成一个集合，然后按照一定规律将部分集合合成一个集合，也就是集合合并。并查集（union-find)适合来描述这类问题。

对于并查集，我们可以将它看成是一个森林，森林是由多棵树组成的，并查集中的一个个集合就可以看作是树。

示例：

二，并查集的结构

并查集的存储结构和树的双亲表示法相似。

所谓双亲表示法，就是在树的节点中，只存储父节点的指针，不存储孩子节点的指针。通过指针可以找到父节点。因为对于一颗树来说，可能有多个孩子，但只有一个父节点。

对于上图中：

节点0的数组值为-4，说明该节点为根节点。

节点6的数组值为0，说明该节点的父节点为0。

节点7的数组值为0，说明该节点的父节点为0。

节点8的数组值为0，说明该节点的父节点为0。

三，并查集的代码实现

并查集主要支持一下操作：

查询（find），查询一个元素在哪个集合中。
合并（union)，将两个集合合并为一个。

1，并查集的大致结构和初始化

class UnionFind
{
public:
   UnionFind(size_t n)
       :_ufs(n,-1)
   {}

   //......
private:
   vector<int> _ufs;
};

2，find操作

在并查集中找到包含x的根

int findRoot(int x)
{
   int root = x;

   while (_ufs[root] >= 0)
       root = _ufs[root];

   return root;
}

3，Union操作

合并两个集合

void Union(int x1, int x2)
{
   int root1 = findRoot(x1);
   int root2 = findRoot(x2);
   if (root1 == root2)
       return; //在同一个集合中

   //这里在合并的时候采用数据量小的向数据量大的合并
   //也就是小树向大树合并
   if (abs(_ufs[root1]) < abs(_ufs[root2]))//root1节点更少
   {
       _ufs[root2] += _ufs[root1];
       _ufs[root1] = root2; //小树合并到大树
   }
   else
   {
       //root2节点更少
       _ufs[root1] += _ufs[root2];
       _ufs[root2] = root1;
   }
}

4，优化

当树比较高时，我们在反复查某个节点的根节点时，每次都会花费大量时间。

优化方法：路径压缩，只要查找某个节点一次，就将查找路径上的所有节点挂到根节点下面。

如图：查找D的根A，查找路径上包含节点B，将节点D和节点B直接挂在根节点A的下面。

//路径压缩
int findRoot(int x)
{int root = x;while (_ufs[root] >= 0)root = _ufs[root];//路径压缩while (_ufs[x] >= 0){int parent = _ufs[x];_ufs[x] = root;   //挂在根节点的下面x = parent;}return root;
}

小结：

上述实现的并查集，支持连续元素。如果是处理非连续元素，需要使用哈希表代替数组（需额处理元素与索引的映射）。

核心思路：

哈希映射：用unordered_map将任意类型元素映射为连续整数ID，内部用数组管理父节点

动态扩容：自动添加新元素，无需预先指定规模。

模板化：支持泛型数据类型（如string等）。

四，并查集的应用场景

连通性检测：判断网络中两个节点是否连通。

最小生成树（Kruskal算法）：动态合并边，避免环。

社交网络分组：快速合并好友关系，查询是否属于同一社交圈。

总结：

并查集通过高效的查找与合并操作，成为处理动态连通性问题的核心数据结构。其优化方法（路径压缩、按秩合并）确保了接近常数的单次操作时间复杂度，适用于大规模数据场景。

其中的按秩合并就是合并集合时小树向大树合并。

省份数量[OJ题]

题目链接：LCR 116. 省份数量 - 力扣（LeetCode）

isConnected[i][j]=1，表示城市i和j连通，连通的城市为一个省份。用并查集将连通的数据放入一个集合，再统计最后的集合个数即可。

class Solution {
public:int findCircleNum(vector<vector<int>>& isConnected) {int n=isConnected.size();vector<int> _ufs(n,-1);//查找根auto find=[&](int x)->int{int root=x;while(_ufs[root]>=0)root=_ufs[root];return root;};for(int i=0;i<n;i++)for(int j=0;j<n;j++){if(isConnected[i][j]==1){//合并i和j集合int rooti=find(i),rootj=find(j);if(rooti!=rootj){_ufs[rooti]+=_ufs[rootj];_ufs[rootj]=rooti;}}}//统计集合数int ret=0;for(auto x:_ufs){if(x<0)ret++;}return ret;}
};