并查集原理
首先需要明确, 并查集是一个森林
在一些应用问题中, 需要将n个不同的元素划分成一些不相交的集合. 开始时, 每个元素自成一个单元素集合, 然后按一定的规律将归于同一组元素的集合合并. 在此过程中要反复用到查询某一个元素归属于哪个集合的运算. 适合于描述这类问题的抽象数据类型称为并查集(union-findset).
举例:
有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担任队长:
一趟旅行之后, 每个小分队成员就互相熟悉, 形成了一个朋友圈, 3个小团体合并成了一个大团体:
仔细观察数组中的下标, 可以得出:
1. 数组中一个位置的值如果为负数, 那它就是树的根, 负数的绝对值就是这棵树的数据的个数.
2. 数组中一个位置的值如果为非负数, 代表该位置值双亲的下标
通过以上例子可知，并查集一般可以解决以下问题:
1. 查找元素属于哪个集合
沿着数组表示的树形关系, 往上一直找到根(即: 树中中元素为负数的位置)
2. 查看两个元素是否属于同一个集合
沿着数组表示的树形关系往上一直找到树的根, 如果根相同表明在同一个集合, 否则不在
3. 将两个集合归并成一个集合
将两个集合中的元素合并
将一个集合名称改成另一个集合的名称
4. 集合的个数
遍历数组, 数组中元素为负数的个数即为集合的个数。
并查集实现
主要实现三个接口, 其中FindRoot接口是Union接口的子函数.
1. 构造函数将数组全部初始化为-1
2. Union是将两个位置所在的并查集合并, 要想合并要先找它们的根看是否在一个并查集, 是的话就不需要合并, 所以先实现FindRoot. 合并注意一个细节, 可以把集合元素少的向集合元素多的去合并, 因为被合并的那个集合所有节点的深度都会+1, 所以让更少的元素集合合并到更多的元素集合可以提高FindRoot的效率.
3. FindRoot 一直查询位置对应的值是不是负值即可
4. SetSize查询共有几个并查集, 统计数组中负数的个数即可.
在查询的过程中我们还可以顺便实现压缩路径的操作:
在不断的Union之后, 可能有的节点的层数会很深, FindRoot的时候需要向上查找很多次, 所以在每一次查找完Root之后, 通过比对 当前位置的直接根 是否等于查找之后的Root, 如果不是说明该节点的层次大于2层, 就可以合并了, 把该节点的下标修改为之前查找到的Root即可, 而且可以顺着该节点依次向上遍历, 可以把路径上所有高度大于2的结点全部合并到Root之下.
#include <iostream>
#include <vector>
class UnionFindSet
{
public:
UnionFindSet(int n)
:ufs(n,-1)
{}
void Union(int i, int j)
{
int rooti = FindRoot(i);
int rootj = FindRoot(j);
if (rooti == rootj)
return;
else
{
//保持rooti为集合内元素多的根, 注意ufs[rooti]内是负值, 数值大的元素反而少
if (ufs[rooti] > ufs[rootj])
std::swap(rooti, rootj);
ufs[rooti] += ufs[rootj];
ufs[rootj] = rooti;
}
}
int FindRoot(int x)
{
int root = x;
while (ufs[root] >= 0)
{
root = ufs[root];
}
//查找途中顺便压缩路径
while(ufs[x] >=0)
{
int lastparent = ufs[x];
ufs[x] = root;
x = lastparent;
}
return root;
}
int SetSize()
{
int ret = 0;
int n = ufs.size();
for (int i = 0; i < n; i++)
{
if (ufs[i] < 0)
ret++;
}
return ret;
}
//判断两个节点是否在同一个并查集, 克鲁斯卡尔算法会用到
bool InSet(size_t a, size_t b)
{
size_t root1 = FindRoot(a);
size_t root2 = FindRoot(b);
return root1 == root2;
}
private:
std::vector<int> ufs;
};并查集解决例题
省份数量
直接把并查集拷贝过来, isConnected[i][j]==1就Union(i,j), 最后返回并查集的个数即可, 只需要调用并查集的两个接口:
class UnionFindSet
{
public:
UnionFindSet(int n)
:ufs(n,-1)
{}
void Union(int i, int j)
{
int rooti = FindRoot(i);
int rootj = FindRoot(j);
if (rooti == rootj)
return;
else
{
if (rooti > rootj)
std::swap(rooti, rootj);//保持rooti为小坐标
ufs[rooti] += ufs[rootj];
ufs[rootj] = rooti;
}
}
int FindRoot(int x)
{
int parent = x;
while (ufs[parent] >= 0)
{
parent = ufs[parent];
}
//查找途中顺便压缩路径
if (x >= 0 && parent != ufs[x])
{
while (x != parent)
{
int lastparent = ufs[x];
ufs[x] = parent;
x = lastparent;
}
}
return parent;
}
int SetSize()
{
int ret = 0;
int n = ufs.size();
for (int i = 0; i < n; i++)
{
if (ufs[i] < 0)
ret++;
}
return ret;
}
private:
std::vector<int> ufs;
};
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected)
{
int x = isConnected.size();
int y = isConnected[0].size();
UnionFindSet s(x);
for(int i = 0; i < x; i++)
{
for(int j = 0; j < y; j++)
{
if(i == j)
continue;
if(isConnected[i][j] == 1)
{
s.Union(i,j);
}
}
}
return s.SetSize();
}
};用并查集的思想也可以, 只不过把并查集的关键代码重写一遍:
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected)
{
int x = isConnected.size();
int y = isConnected[0].size();
vector<int> ufs(x,-1);
auto FindRoot = [&ufs](int x)
{
int parent = x;
while(ufs[parent] >= 0)
{
parent = ufs[parent];
}
return parent;
};
for(int i = 0; i < x; i++)
{
for(int j = 0; j < y; 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 ret =0;
for(auto e:ufs)
{
if(e <0)
ret++;
}
return ret;
}
};等式方程的可满足性
将相等的元素合并到一个并查集, 最后查询不相等的元素的是不是在一个并查集下即可:
class Solution {
public:
bool equationsPossible(vector<string>& equations)
{
vector<int> ufs(26,-1);
auto FindRoot = [&ufs](int x)
{
while(ufs[x] >=0)
{
x = ufs[x];
}
return x;
};
for(auto& equation: equations)
{
if(equation[1] == '=')
{
int root1 = FindRoot(equation[0]-'a');
int root2 = FindRoot(equation[3]-'a');
if(root1 != root2)
{
ufs[root1] += ufs[root2];
ufs[root2] = root1;
}
}
}
for(auto& equation: equations)
{
if(equation[1] == '!')
{
int root1 = FindRoot(equation[0]-'a');
int root2 = FindRoot(equation[3]-'a');
if(root1 == root2)
return false;
}
}
return true;
}
};