文章目录
- 引言
- 一、并查集的概念
- 二、并查集的模拟实现
- 2.1 成员变量与默认成员函数
- 2.2 FindRoot
- 2.3 Union
- 2.4 InSet
- 2.5 SetSize
- 三、等价类划分
引言
数据结构世界——并查集（Union Find Set)
一、并查集的概念
并查集，又称为Disjoint Set，是一种简单的用途广泛的集合。并查集拥有多个集合，通过某种规则不断合并集合，常用于查找和判断一个元素归属于哪个集合。
并查集常用森林进行表示，用数组进行实现（类似二叉堆）。链接方式采用双亲表示法，每个根存储这棵树（当前集合）的元素数量，其余结点存储双亲的下标。
二、并查集的模拟实现
2.1 成员变量与默认成员函数
template<class T>
class UnionFindSet
{
public:UnionFindSet(int n): _ufs(n, -1){}
private:vector<int> _ufs;
};
细节：初始化构造时，将所有元素设为-1，代表每个元素是一个单独的集合。
2.2 FindRoot
//给一个元素的下标，返回这个集合内根的下标
int FindRoot(int pos)
{int root = pos;while (_ufs[root] >= 0){root = _ufs[root];}//路径压缩int cur = pos;while (_ufs[cur] >= 0){int next = _ufs[cur];_ufs[cur] = root;cur = next;}return root;
}
细节：
- FindRoot函数为并查集实现的核心函数，这里实现了
查找和路径压缩优化。 - 负数代表根，那么只要存储为正，则一直向上查找。
- 路径压缩，即将查找路径上的结点，重新直接链接在根结点上，防止路径过深导致查找效率低下。
2.3 Union
void Union(int pos1, int pos2)
{int root1 = FindRoot(pos1);int root2 = FindRoot(pos2);//同在一个集合内不用合并if (root1 != root2){//数据量小的往数据量大的合并if (abs(_ufs[root1]) < abs(_ufs[root2])){swap(root1, root2);}_ufs[root1] += _ufs[root2];_ufs[root2] = root1;}
}
细节：
- 集合的合并，是两棵树的
根相连，从而合并为一棵树。 - 先对两个元素进行寻根，只有在不同的集合才进行合并。
- 合并时按照数据量小的往数据量大的合并，防止合并后路径过深。
2.4 InSet
bool InSet(int pos1, int pos2)
{return FindRoot(pos1) == FindRoot(pos2);
}
细节：通过判断两个元素的根是否相等，来判断是否在同一集合。
2.5 SetSize
int SetSize()
{int n = 0;for (auto x : _ufs){if (x < 0) ++n;}return n;
}
细节：遍历数组，记录根（存储负数）的个数，从而计算集合的数量。
三、等价类划分
并查集的应用就是等价类划分。
思路：关于城市是否连通，可以用并查集进行合并与查找。
class Solution
{
public:int findCircleNum(vector<vector<int>>& isConnected){int n = isConnected.size();vector<int> ufs(n, -1);auto FindRoot = [&ufs](int pos){int cur = pos;while(ufs[cur] >= 0){cur = ufs[cur];}return cur;};for(int i=0; i<n; ++i){for(int j=0; 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;}}}}int cnt = 0;for(auto x : ufs){if(x < 0) ++cnt;}return cnt;}
};
细节：
- 由于解题时写一个并查集不合适，所以只保留核心函数和数组。
- FindRoot函数可以用lambda表达式来实现，引用捕捉ufs。
- 遍历矩阵的过程中，实现Union函数的思想，将相连的城市合并到一个集合。
- 最后记录集合的个数，即为省份的数量。
class Solution
{
public:bool equationsPossible(vector<string>& equations){vector<int> ufs(26, -1);auto FindRoot = [&ufs](int pos){int cur = pos;while(ufs[cur] >= 0){cur = ufs[cur];}return cur;};for(auto& s : equations){int root1 = FindRoot(s[0]-'a');int root2 = FindRoot(s[3]-'a');if(s[1] == '='){if(root1 != root2){ufs[root1] += ufs[root2];ufs[root2] = root1;}}}for(auto& s : equations){int root1 = FindRoot(s[0]-'a');int root2 = FindRoot(s[3]-'a');if(s[1] == '!'){if(root1 == root2) return false;}}return true;}
};
细节：
- 部分细节同上。
- 遍历字符串数组，将相等的字符都合并到一个集合中。
- 再遍历一遍，遇到不相等的字符，判断是否在同一集合，从而排除矛盾。
所以，并查集在运用的过程中，就是不断将等价的东西划分在一起，不断合并，便于指定元素属于哪个集合的查找。
