在一些应用问题中,需要将 n 个不同的元素划分成一些不相交的集合。开始时,每个元素自成一个单元素集合,然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-find set)。
例如有 10 个数字如下,开始时每个元素单独成为一个集体,所以我们可以使用数组模拟,用数组下标标记不同的元素,内容如果是 -1 表示自己单独是一个集合,并且只有自己一个元素;如果是负几,就代表这个集合有几个元素;如果是大于0,代表自己是一个集合的元素,该集合的数组下标就是这个大于0的数:
我们简单对这些数进行分组:
用数组表示如下:
所以总结一下:
假设我们将 1 下标的集合合并到 0 下标中,结果如下:
现在 0 下标的集合有 7 个元素, 2 下标的集合有3个人,总共两个集合。
通过以上例子可知,并查集一般可以解决以下问题:
并查集的基本实现如下代码所示:
class UnionFind
{
public:
// 构造函数初始化数组
UnionFind(size_t size)
:_uf(size, -1)
{}
// 找到根的下标
int FindRoot(int index)
{
while(_uf[index] >= 0){
index = _uf[index];
}
return index;
}
// 合并两个集合
bool Union(int index1, int index2)
{
int root1 = FindRoot(index1);
int root2 = FindRoot(index2);
// 已经在一个集合中
if(root1 == root2) return false;
_uf[root1] += _uf[root2];
_uf[root2] = root1;
return true;
}
// 返回集合的数量
size_t Count() const
{
size_t cnt = 0;
for(auto e : _uf){
if(e < 0){
cnt++;
}
}
return cnt;
}
private:
std::vector<int> _uf;
};
下面我们看两道题对于并查集的应用:
题目:有 n 个城市,其中一些彼此相连,另一些没有相连。如果城市 a 与城市 b 直接相连,且城市 b 与城市 c 直接相连,那么城市 a 与城市 c 间接相连。
省份是一组直接或间接相连的城市,组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ,其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连,而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中省份的数量。
示例一:
输入:isConnected = [[1,1,0],[1,1,0],[0,0,1]] 输出:2
示例二:
输入:isConnected = [[1,0,0],[0,1,0],[0,0,1]] 输出:3
提示:
思路:我们只需要遍历这个二维数组,只要是值为1的位置,我们就将这个位置的下标放入一个集合中,我们同样使用数组模拟并查集,最后统计并查集中小于0的个数即是省份的数量。代码如下:
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
vector<int> uf(isConnected.size(), -1);
auto FindRoot = [&uf](int index)
{
while(uf[index] >= 0){
index = uf[index];
}
return index;
};
for(int i = 0; i < isConnected.size(); i++){
for(int j = i + 1; j < isConnected[i].size(); j++){
if(isConnected[i][j] == 1){
int root1 = FindRoot(i);
int root2 = FindRoot(j);
if(root1 != root2){
uf[root1] += uf[root2];
uf[root2] = root1;
}
}
}
}
int cnt = 0;
for(auto e : uf){
if(e < 0){
cnt++;
}
}
return cnt;
}
};
题目:给定一个由表示变量之间关系的字符串方程组成的数组,每个字符串方程 equations[i] 的长度为 4,并采用两种不同的形式之一:“a==b” 或 “a!=b”。在这里,a 和 b 是小写字母(不一定不同),表示单字母变量名。
只有当可以将整数分配给变量名,以便满足所有给定的方程时才返回 true,否则返回 false。
示例 1: 输入:[“a==b”,“b!=a”] 输出:false 解释:如果我们指定,a = 1 且 b = 1,那么可以满足第一个方程,但无法满足第二个方程。没有办法分配变量同时满足这两个方程。
示例 2: 输入:[“ba","ab”] 输出:true 解释:我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。
示例 3: 输入:[“ab","bc”,“a==c”] 输出:true
示例 4: 输入:[“ab",“b!=c”,"ca”] 输出:false
示例 5: 输入:[“cc","bd”,“x!=z”] 输出:true
提示:
思路:因为只是对小写字母之间判断是否有相悖的结论,所以我们可以先遍历一遍,将所有相等的放入一个并查集中;然后第二次遍历就找不相等的,如果这两个不相等的元素出现在并查集中,说明结论相悖,直接返回 false;否则返回 true;代码如下:
class Solution {
public:
bool equationsPossible(vector<string>& equations)
{
vector<int> uf(26, -1);
auto FindRoot = [&uf](int index)
{
while(uf[index] >= 0){
index = uf[index];
}
return index;
};
// 先将相同的元素放入一个集合
for(auto& str : equations){
int root1 = FindRoot(str[0] - 'a');
int root2 = FindRoot(str[3] - 'a');
if(str[1] == '='){
if(root1 != root2){
uf[root1] += uf[root2];
uf[root2] = root1;
}
}
}
for(auto& str : equations){
int root1 = FindRoot(str[0] - 'a');
int root2 = FindRoot(str[3] - 'a');
// 相悖
if(str[1] == '!'){
if(root1 == root2){
return false;
}
}
}
return true;
}
};