[数据结构#1] 并查集 | FindRoot | Union | 优化 | 应用

目录

1. 并查集原理

问题背景

名称与编号映射

数据结构设计

2. 并查集基本操作

(1) 初始化

(2) 查询根节点 (FindRoot)

(3) 合并集合 (Union)

(4) 集合操作总结

并查集优化

(1) 路径压缩

(2) 按秩合并

3. 并查集的应用

(1) 统计省份数量

(2) 判断等式方程是否成立

---

并查集是一种用于处理 元素分组和集合操作 的数据结构，主要功能是支持以下两种操作：

1. 合并：将两个集合合并成一个集合。
2. 查询：判断某个元素属于哪个集合。

并查集实际上是由多棵 互不相交的树 组成的森林，以下是详细的整理内容。

---

1. 并查集原理

问题背景

在一些问题中，需要将 n  个不同的元素划分为若干个互不相交的集合，并支持以下操作：

• 查询某个元素所属的集合。
• 合并两个集合。

例如，某公司校招的 10 名学生，分别来自不同地区，起初各自独立。根据他们的交流情况，可以将其分为几个小团体。通过并查集，可以很好地表示这些分组关系，并实现高效的集合操作。

• 首先先给这些学生进行编号：{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 给以下数组用来存储该小集体，数组中的数字代表：该小集体中具有成员的个数。(负号下文解释)

继续往下看，如何描述他们之间的关系呢？

西安学生小分队s1={0,6,7,8}，成都学生小分队s2={1,4,9}，武汉学生小分队s3={2,3,5}就相互认识了，10个人形成了三个小团体。假设右三个群主0,1,2担任队长，负责大家的出行。如何表示这三个集合呢？

很简单，把他们建立三颗树形结构。一个数据结构有多颗树不就是之前所说的森林了。如何建树呢？一个集体随便选取一个节点作根，剩下节点取做它的孩子。

那我们如何来表示这里的集合结构呢？

并查集是森林，森林是由多个树组成，这里用两层来表示这里的关系。

1. 像堆类似，用数组下标表示关系
2. 双亲表示法（存储双亲的下标）

仔细观察数组中内融化，可以得出以下结论：

1. 数组的下标对应集合中元素的编号
2. 数组中如果为负数，负号代表根，数字绝对值 代表该集合中元素个数
3. 数组中如果为非负数，代表该元素双亲在数组中的下标

合并过程：

继续往下看，如何将已经有的集合合并呢？ 刚才都是独立的集合直接合并，现在是已经有集合怎么合并呢?

比如说在公司工作一段时间后，西安小分队中8号同学与成都小分队4号同学奇迹般的走到了一起，两个小圈子的学生相互介绍，最后成为了一个小圈子：怎么合并呢？

• 不能直接合并，而是找到两个数的根，让根合并。

找根很简单，看自己位置保存的是不是负数，如果是负数自己就是根了，如果不是负数保存的就是双亲的下标了，就去看看双亲下标保存的是不是负数，不是负数还跳，直到找到双亲下标保存的值是负数，这个下标也就是根了。

把1下标的值加道0下标，然后1下标位置保存0下标。

通过以上例子可知，并查集一般可以解决一下问题：

1. 查找元素属于哪个集合
   沿着数组表示树形关系以上一直找到根(即：树中中元素为负数的位置)
2. 查看两个元素 是否属于同一个集合
   沿着数组表示的树形关系往上一直找到树的根，如果根相同表明在同一个集合，否则不在
3. 将两个集 合归并成一个集合
   将两个集合中的元素合并
   将一个集合名称改成另一个集合的名称
4. 集合的个数
   遍历数组，数组中元素 为负数的个数即为集合的个数。

下面就实现一下并查集~

---

名称与编号映射

• 可能会有这样的问题，内部给他们编号，万一外面给的是10个人给的是名字，我怎么知道谁是那个编号呢？怎么解决？

借助vector，map建立对应映射关系！

• vector：存储名称列表，通过下标快速找到名字。
• map：建立名字到编号的映射关系。

代码示例：

template<class T>
class UnionFindSet
{
public:
UnionFindSet(const T* a, size_t sz)
{for (int i = 0; i < sz; ++i){_a.push_back(a[i]);//将数组中元素添加到vector中_IndexMap[a[i]] = i;//将人映射到hash中}
}private:
vector<T> _a;          //编号找人
map<T, int> _IndexMap; //人找编号
};int main()
{string arr[] = { "张三","李四","王五","赵六" };UnionFindSet<string> ufs(arr, 4);return 0;
}

• _a.push_back(a[i]);：这一行代码将数组 a 的第 i 个元素添加到成员变量 _a 向量的末尾。这里 a 是构造函数参数中的一个指针，指向传入的数组，而 a[i] 则是该数组中第 i 个位置的元素。
• _IndexMap[a[i]] = i;：此行代码则是在建立一个映射关系。它使用成员变量 _IndexMap，这是一个从类型 T 映射到整数类型的关联容器（map）。这里它将数组 a 的第 i 个元素作为键，i 作为值插入到 _IndexMap 中。因此，以后当我们知道某个人的名字时，可以通过 _IndexMap 快速查找这个人在原始数组中的索引位置。

这样不管是给下标还是给名字都可以解决这里的问题。

---

数据结构设计

并查集通过一个数组表示关系：

• 数组下标 表示集合中的元素编号。
• 数组值 用于表示该元素的父节点或根节点的信息。

• • 负数：表示集合的根，绝对值为该集合中元素的个数。
  • 非负数：表示其父节点在数组中的下标。

双亲表示法：每个节点存储其父节点的位置，通过不断向上查找父节点，最终可以找到集合的根节点。

---

2. 并查集基本操作

(1) 初始化

• 初始时，每个元素自成一个集合，数组值均为 -1，表示每个集合的大小为 1。

UnionFindSet(int sz): _ufs(sz, -1) {}  // 初始化，大小为 sz，每个位置存储 -1

---

(2) 查询根节点 (FindRoot)

• 找到某个元素所在集合的根节点。
• 如果当前节点的父节点为负数，则该节点是根节点。
• 路径压缩：为了提高查询效率，将查询路径上的所有节点直接连接到根节点。

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;
}

这里在补充说一点，并查集 路径压缩 的问题。比如集合是下面这个样子，要从9找到根需要跳很多层。影响找根的效率，能不能想到什么办法把路径压缩一下呢？

其实也很简单 ，反正都是在同一个集合，是不是直接可以考虑把下面的直接压到根的下面做根的孩子。这样就变成了一层。如果数据量很多层数很高压缩路径后这样很不错。

• 一般在查找根的时候去压缩。
• 查找谁就把它这一条路径压缩。
• 找到根之后判断一下，如果它的父亲就是根就不用压缩，如果不是说明中间有间隔层，然后就可以把这条路径压缩。

比如是这个4，首先先把4变成2的孩子，然后将4的父亲1也去变成2的孩子，这条路径都可以变成2的孩子。

---

(3) 合并集合 (Union)

• 并查集 除了路径压缩，还有一种提高效率的方式，比如两个集合 合并的时候

• • 小集合向大集合合并，以减少树的深度。

• 实现步骤：

• • 找到两个集合的根节点。
  • 如果根节点相同，说明两个元素已在同一个集合中，无需合并。
  • 否则，将小集合的根指向大集合的根，并更新集合大小。

bool Union(int x1, int x2) {int root1 = FindRoot(x1);int root2 = FindRoot(x2);if (root1 == root2) return false;// 控制小集合向大集合合并if (abs(_ufs[root1]) < abs(_ufs[root2])) {swap(root1, root2);}_ufs[root1] += _ufs[root2];_ufs[root2] = root1;return true;
}

---

(4) 集合操作总结

• 查找元素所属集合：找到其根节点。
• 判断两个元素是否属于同一集合：检查它们的根节点是否相同。
• 统计集合数量：统计数组中负数的个数，即为集合的数量。

---

并查集优化

(1) 路径压缩

• 在查询根节点时，将路径上的节点直接连接到根节点，减少树的高度。
• 优化后的查找复杂度接近 O(1) 。

(2) 按秩合并

• 优先将元素较少的集合合并到元素较多的集合，进一步减少树的高度。
• 实现方法：比较根节点的绝对值，选择小集合向大集合合并。

完整代码：

#pragma once#include<iostream>
#include<vector>
#include<map>using namespace std;//template<class T>
//class UnionFindSet
//{
//public:
//	UnionFindSet(const T* a, size_t sz)
//	{
//		for (int i = 0; i < sz; ++i)
//		{
//			_a.push_back(a[i]);
//			_IndexMap[a[i]] = i;
//		}
//	}
//
//
//private:
//	vector<T> _a;          //编号找人
//	map<T, int> _IndexMap; //人找编号
//};class UnionFindSet
{
public:UnionFindSet(int sz):_ufs(sz,-1)// 初始时，将数组中元素全部设置为1{}bool Union(int x1, int x2){int root1 = FindRoot(x1);int root2 = FindRoot(x2);// x1已经与x2在同一个集合if (root1 == root2)return false;//控制数据量小的往大的集合合并if (abs(_ufs[root1]) < abs(_ufs[root2])){swap(root1, root2);}// 将两个集合中元素合并_ufs[root1] += _ufs[root2];// 将其中一个集合名称改变成另外一个_ufs[root2] = root1;return true;}// 给一个元素的编号，找到该元素所在集合的名称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;}bool IsSet(int x1, int x2){return FindRoot(x1) == FindRoot(x2);}// 数组中负数的个数，即为集合的个数size_t SetSize(){size_t count = 0;for (auto e : _ufs){if (e < 0) ++count;}return count;}private:vector<int> _ufs;
};

---

3. 并查集的应用

(1) 统计省份数量

题目链接：[LCR 116. 省份数量]

• 思路：

• • 使用并查集，将直接连接的城市合并到同一个集合。
  • 遍历矩阵，统计并查集中集合的数量。

代码实现：

int findCircleNum(vector<vector<int>>& isConnected) {int n = isConnected.size();vector<int> ufs(n, -1);auto Findroot = [&](int x) {while (ufs[x] >= 0) {x = ufs[x];}return x;};for (int i = 0; i < n; ++i) {for (int j = i + 1; j < n; ++j) {if (isConnected[i][j] == 1) {int root1 = Findroot(i);int root2 = Findroot(j);if (root1 != root2) {ufs[root1] += ufs[root2];ufs[root2] = root1;}}}}return count_if(ufs.begin(), ufs.end(), [](int x) { return x < 0; });
}

---

(2) 判断等式方程是否成立

题目链接：[990. 等式方程的可满足性]

• 思路：

• • 将所有“相等”的变量合并到同一个集合。
  • 遍历“不等”关系，若两个变量属于同一个集合，则矛盾。

代码实现：

bool equationsPossible(vector<string>& equations) {vector<int> ufs(26, -1);auto Findroot = [&](int x) {while (ufs[x] >= 0) {x = ufs[x];}return x;};// 合并“相等”关系for (auto& eq : equations) {if (eq[1] == '=') {int root1 = Findroot(eq[0] - 'a');int root2 = Findroot(eq[3] - 'a');if (root1 != root2) {ufs[root1] += ufs[root2];ufs[root2] = root1;}}}// 检查“不等”关系for (auto& eq : equations) {if (eq[1] == '!') {int root1 = Findroot(eq[0] - 'a');int root2 = Findroot(eq[3] - 'a');if (root1 == root2) return false;}}return true;
}

并查集 使用场景：两极性的集合划分

连接或不连接，相等或不相等 的判断 

---

并查集是一种高效的数据结构，支持快速的 合并 和 查询 操作，并在路径压缩和按秩合并优化下性能接近常数时间。