DS并查集(17)

---

前言

  其实我一开始是想直接讲图的，但是但是考虑的图的 Kruskal 算法要用到，就先讲解下并查集吧！

---

一、何为并查集？

  并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题
  并查集通常用森林来表示，森林中的每棵树表示一个集合，树中的结点对应一个元素

这可能太抽象了，我们举个具体的例子：

  以朋友圈为例，现在有10个人（从0开始编号），刚开始这10个人互不认识，所以各自属于一个集合

  并查集会用一个数组来表示这10个人之间的关系，数组的下标对应就是这10个人的编号，刚开始时数组中的元素都初始化为-1

数组中某个位置的值为负数，表示该位置是树的根，这个负数的绝对值表示的这棵树（集合）中数据的个数，因为刚开始每个人各自属于一个集合，所以将数组中的位置都初始化为-1

  后来这10个人之间通过相互认识，最终形成了三个朋友圈

  此时并查集数组中各个位置的值如下

数组中某个位置的值为非负数，表示该位置不是树的根，这个非负数的值就是这个结点的父结点的编号

  后来4号和8号又通过某种机遇互相认识了，这时他们所在的两个集合就需要进行合并，最终就变成了两个朋友圈

  需要注意的是，在根据两个元素合并两个集合时，需要先分别找到这两个元素所在集合的根结点，然后再将一个集合合并到另一个集合，并且合并后需要更新数组中根结点的值

为什么要找根节点？

1. 如果这两个元素所在集合的根结点相同，说明这两个元素本身就在同一个集合，无需合并
2. 合并集合后需要更新这两个集合的根结点的值

  而要判断两个元素是否在同一个集合，也就是判断这两个元素所在集合的根结点是否相同

二、并查集的实现？

  首先我们要想元素的下标是否对应，如果无法对应的话，我们一般利用容器 map 来存储元素的下标映射

template<class T>
class UnionFindSet
{
public:UnionFindSet(const T* a, size_t n){for (size_t i = 0 ; i < n ; i++) {_a.push_back(a[i]);_indexMap[a[i]] = i;}}
private:vector<T> _a; // 编号找人map<T, int> _indexMap;// 人找编号
};

  不过在这里，我们假设给的就是下标，也就是说私有成员就只有一个 vector< int > _ufs 了

并查集的初始化

  并查集中会用一个数组来维护各个结点之间的关系，在初始化并查集时，根据元素的个数开辟数组空间，并将数组中的元素初始化为 -1 即可

//构造函数
UnionFindSet(int n):_ufs(n, -1) //初始时各个元素自成一个集合
{}

查找元素所在的集合

查找逻辑如下：

• 如果元素对应下标位置存储的是负数，则说明该元素即为根结点，返回该元素即可。
• 如果元素对应下标位置存储的是非负数，则跳转到其父结点的位置继续查找根结点。

    int FindRoot(int x){int root = x;while (_ufs[root] >= 0){root = _ufs[root];}return root;}

判断两个元素是否在同一个集合

    bool isInset(int x1, int x2){return FindRoot(x1) == FindRoot(x2);}

合并两个元素所在的集合

合并逻辑如下：

• 分别找到两个元素所在集合的根结点。
• 如果这两个元素所在集合的根结点相同，则无需合并，如果这两个元素所在集合的根结点不同，则将小集合合并到大集合上。
• 将小集合根结点的值累加到大集合的根结点上，使得大集合根结点的值的绝对值等于两个集合中元素的总数。
• 将小集合根结点的值改为大集合根结点的编号，也就是让小集合的根结点作为大集合根结点的孩子，使得两个集合变为一个集合。

    // 合并两个集合void Union(int x1, int x2){int root1 = FindRoot(x1);int root2 = FindRoot(x2);// 如果本身就在一个集合，那么无需合并if (root1 == root2) return ;// 合并的时候，作为孩子，其深度会增加一层// 因此，理论上来说，数据量小的作孩子// 如果有需求下标小的作根，则交换一下root// if (root1 > root2) swap(root1, root2); // 按照下标大小if (abs(_ufs[root1]) < abs(_ufs[root2])) swap(root1, root2); // 按照数据量大小// 如果不在同一个集合，则默认认为把x2代表集合合并到x1上，即x1作根，x2作子_ufs[root1] += _ufs[root2];// 将x2代表集合的名称改为x1_ufs[root2] = root1;}

获取并查集中集合的个数

  要获取并查集中集合的个数，本质就是统计数组中负值（根结点）的个数

    size_t SetSize(){size_t size = 0;for (size_t i = 0 ; i < _ufs.size() ; i++){if (_ufs[i] < 0) size++;}return size;}

并查集的路径压缩

  当数据量很大的时候，并查集中树的层数可能会变得很高，这时再查找一个元素所在集合的根结点时就需要往上走很多层，这时可以考虑进行路径压缩

  路径压缩一般会在查找根结点时进行，当根据一个结点查找其根结点时，该路径上所有的结点都会被压缩，最终这些结点会直接被挂在根结点下，下次再根据这些结点查找根结点时就能快速找到根结点

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

三、来两道题练练手？

省份的数量

LCR 116. 省份数量

思路其实是很明确的：

1. 定义一个长度为 n 的数组充当并查集，并将数组中的元素初始化为 -1，表示各个城市各自是一个省份。
2. 根据所给矩阵，对并查集中的各个集合进行合并。
3. 并查集中集合的个数即为省份的数量

class Solution
{
public:int findCircleNum(vector<vector<int>>& isConnected){UnionFindSet ufs(isConnected.size());for (size_t i = 0 ; i < isConnected.size() ; i++){for (size_t j = 0 ; j < isConnected[i].size() ; j++){if (isConnected[i][j]){ufs.Union(i, j);}}}return ufs.SetSize();}};

等式方程的可满足性

990. 等式方程的可满足性

思路其实也是很明确的：

1. 定义一个长度为26（变量为小写字母）的数组充当并查集，并将数组中的元素初始化为-1，表示各个字母只有自己等于自己。
2. 根据字符串方程组中的等式，对并查集中的各个集合进行合并（每个集合中的元素都是相等的）。
3. 根据并查集，对字符串方程组中的不等式进行验证，如果两个不相等的变量出现在同一个集合中，则返回 false 。

class Solution
{
public:bool equationsPossible(vector<string>& equations){UnionFindSet ufs(26);for (const auto& str : equations){if (str[1] == '='){ufs.Union(str[0] - 'a', str[3] - 'a');}}for (const auto& str : equations){if (str[1] == '!'){int root1 = ufs.FindRoot(str[0] - 'a');int root2 = ufs.FindRoot(str[3] - 'a');if (root1 == root2) return false;}}return true;}
};

---

总结

  其实，从这里开始的数据结构就比较困难了
  图、跳表、B树，它们要来了！！！