并查集原理及模拟实现
目录
1.并查集的原理
(1)基本概念
(2)场景示例
(3)示例总结 , 并查集一般可以有如下几个功能
2.并查集的模拟实现
3.并查集的应用
(1)省份数量
(2)等式方程的可满足性
1.并查集的原理
(1)基本概念
在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个
单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一
个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-fifind
set)。
(2)场景示例
①比如：某公司今年校招全国总共招生10人，西安招4人，成都招3人，武汉招3人，10个人来自不 同的学校，起先互不相识，每个学生都是一个独立的小团体，现给这些学生进行编号：{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 给以下数组用来存储该小集体，数组中的数字代表：该小集体中具有成员的个 数。
- 初始状态给的是-1，表示10颗树，10集合(10个根节点)
- 负数表示根 , 绝对值是这棵树的成员个数
- 与堆类似，用下标表示关系，双亲表示法
②毕业后，学生们要去公司上班，每个地方的学生自发组织成小分队一起上路，于是： 西安学生小分队s1={0,6,7,8}，成都学生小分队s2={1,4,9}，武汉学生小分队s3={2,3,5}就相互认识 了，10个人形成了三个小团体。假设右三个群主0,1,2担任队长，负责大家的出行。
③一趟火车之旅后，每个小分队成员就互相熟悉，成为了一个朋友圈。
- 如果一个位置值是负数,那他就是树的根，这个负数绝对值就是这颗树的数据个数。
- 如果一个位置值是正数，那他就是双亲的下标
④在公司工作一段时间后，西安小分队中8号同学与成都小分队1号同学奇迹般的走到了一起，两个 小圈子的学生相互介绍，最后成为了一个小圈子：现在0集合有7个人，2集合有3个人，
(3)示例总结 , 并查集一般可以有如下几个功能
①查找元素属于哪个集合
- 沿着数组表示树形关系以上一直找到根(即：树中中元素为负数的位置)
②查看两个元素是否属于同一个集合
- 沿着数组表示的树形关系往上一直找到树的根，如果根相同表明在同一个集合，否则不在
③将两个集合归并成一个集合
- 将两个集合中的元素合并
- 将一个集合名称改成另一个集合的名称
④集合的个数
- 遍历数组，数组中元素为负数的个数即为集合的个数。
2.并查集的模拟实现
(1)查找元素属于哪个集合
- 通过迭代的方式找到根节点
- 如果该节点双亲的值 >= 0 代表双亲也是某棵树的子节点需要继续向上寻找
- 如果该节点双亲的值 < 0 即为根节点，返回根节点的下标
int FindRoot(int x) //找到节点的根节点
{
int parent = x;
while (_ufs[parent] >= 0) //该节点是树的子节点
{
parent = _ufs[parent]; //向上迭代
}
return parent; //返回的是根的下标
}
补充: 路径压缩(只有当元素的量级很高时采用)
①基本思路
②代码实现
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; //返回的是根的下标
}
(2) 查看两个元素是否属于同一个集合
- 两个元素是否在同一个集合即查看是否有相同的根节点
bool InSet(int x1,int x2) //x1,x2是否在同一个集合中，即一个树中
{
int root1 = FindRoot(x1);
int root2 = FindRoot(x2);
return root1 == root2 ;
}
(3)将两个集合归并成一个集合
- 先找到两个集合的根节点
- 如果两个集合不同，将两个根节点合并
- 最好是将小的集合 合并到 大的集合，这样以后子节点找根节点时找的层数就少了
void Union(int x1, int x2) //将两个数合并到一个集合中
{
int root1 = FindRoot(x1);
int root2 = FindRoot(x2);
if(abs(_ufs[root1]) < abs(_ufs[root2])) //abs取绝对值
swap(root1,root2);
//两个在同一个集合
if (root1 != root2)
{
_ufs[root1] += _ufs[root2]; //合并节点个数，谁合并谁都行
_ufs[root2] = root1; //存下标
}
}
(4)集合的个数
- 找到数组中值为负数的个数
size_t SetSize() //返回集合的个数，即几棵树
{
size_t size = 0;
for (size_t i = 0 ; i < _ufs.size() ;++i)
{
if (_ufs[i] < 0)
{
++size;
}
}
return size;
}
(5)总体代码
#pragma once
#include<vector>
class UnionFindSet
{
public:
UnionFindSet(size_t n)
:_ufs(n, -1)
{}
void Union(int x1, int x2) //将两个数合并到一个集合中
{
int root1 = FindRoot(x1);
int root2 = FindRoot(x2);
if(abs(_ufs[root1]) < abs(_ufs[root2])) //abs取绝对值
swap(root1,root2);
//两个在同一个集合
if (root1 != root2)
{
_ufs[root1] += _ufs[root2]; //合并节点个数，谁合并谁都行
_ufs[root2] = root1; //存下标
}
}
int FindRoot(int x) //找到节点的根节点
{
int parent = x;
while (_ufs[parent] >= 0) //该节点是树的子节点
{
parent = _ufs[parent];
}
return parent; //返回的是根的下标
}
bool InSet(int x1,int x2) //x1,x2是否在同一个集合中，即一个树中
{
int root1 = FindRoot(x1);
int root2 = FindRoot(x2);
return root1 == root2 ;
}
size_t SetSize() //返回集合的个数，即几棵树
{
size_t size = 0;
for (size_t i = 0 ; i < _ufs.size() ;++i)
{
if (_ufs[i] < 0)
{
++size;
}
}
return size;
}
private:
std::vector<int> _ufs;
};
3.并查集的应用
(1)省份数量
①实现完整并查集
class UnionFindSet
{
public:
UnionFindSet(size_t n)
:_ufs(n, -1)
{}
void Union(int x1, int x2) //将两个数合并到一个集合中
{
int root1 = FindRoot(x1);
int root2 = FindRoot(x2);
//两个在同一个集合
if (root1 != root2)
{
_ufs[root1] += _ufs[root2]; //合并节点个数，谁合并谁都行
_ufs[root2] = root1; //存下标
}
}
int FindRoot(int x) //找到节点的根节点
{
int parent = x;
while (_ufs[parent] >= 0) //该节点是树的子节点
{
parent = _ufs[parent];
}
return parent; //返回的是根的下标
}
bool InSet(int x1,int x2) //x1,x2是否在同一个集合中，即一个树中
{
int root1 = FindRoot(x1);
int root2 = FindRoot(x2);
return root1 == root2 ;
}
size_t SetSize() //返回集合的个数，即几棵树
{
size_t size = 0;
for (size_t i = 0 ; i < _ufs.size() ;++i)
{
if (_ufs[i] < 0)
{
++size;
}
}
return size;
}
private:
std::vector<int> _ufs;
};
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected)
{
int n = isConnected.size();
UnionFindSet ufs(n);
for(int i = 0 ;i < n;++i)
{
for(int j = 0; j<i ; ++j)
{
if(isConnected[i][j] == 1)
{
ufs.Union(i,j);
}
}
}
return ufs.SetSize();
}
};②简单实现并查集
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected)
{
//实现并查集的简单逻辑
int num = isConnected.size();
vector<int> ufs(num,-1);
//lambda表达式 找root
auto FindRoot = [&ufs](int x){
while(ufs[x] >=0 )
x = ufs[x];
return x;
};
for(int i = 0 ;i < num;++i)
{
for(int j = 0; j<i ; ++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 count = 0;
for(const auto& e : ufs)//找有几个集合
{
if(e < 0)
++count;
}
return count;
}
};
(2)等式方程的可满足性
①实现完整并查集
class UnionFindSet
{
public:
UnionFindSet(size_t n)
:_ufs(n, -1)
{}
void Union(int x1, int x2) //将两个数合并到一个集合中
{
int root1 = FindRoot(x1);
int root2 = FindRoot(x2);
//两个在同一个集合
if (root1 != root2)
{
_ufs[root1] += _ufs[root2]; //合并节点个数，谁合并谁都行
_ufs[root2] = root1; //存下标
}
}
int FindRoot(int x) //找到节点的根节点
{
int parent = x;
while (_ufs[parent] >= 0) //该节点是树的子节点
{
parent = _ufs[parent];
}
return parent; //返回的是根的下标
}
bool InSet(int x1,int x2) //x1,x2是否在同一个集合中，即一个树中
{
int root1 = FindRoot(x1);
int root2 = FindRoot(x2);
return root1 == root2 ;
}
size_t SetSize() //返回集合的个数，即几棵树
{
size_t size = 0;
for (size_t i = 0 ; i < _ufs.size() ;++i)
{
if (_ufs[i] < 0)
{
++size;
}
}
return size;
}
private:
std::vector<int> _ufs;
};
class Solution {
public:
bool equationsPossible(vector<string>& equations)
{
int n = equations.size();
UnionFindSet ufs(26); //最多26个字母
//第一遍，先把相等的值加到一个集合里
for(int i = 0 ; i < n;++i)
{
if(equations[i][1] == '=')
{
int left = equations[i][0]-'a';
int right = equations[i][3]-'a';
ufs.Union(left,right);
}
}
//第二遍，判断不等的值在不在一个集合里，在就相悖了
for(int i = 0 ; i < n;++i)
{
if(equations[i][1] == '!')
{
int left = equations[i][0]-'a';
int right = equations[i][3]-'a';
int root1 = ufs.FindRoot(left);
int root2 = ufs.FindRoot(right);
if(root1 == root2)
return false;
}
}
return true;
}
};②简单实现并查集
class Solution {
public:
bool equationsPossible(vector<string>& equations) //模拟并查集
{
int n = equations.size();
vector<int> ufs(26,-1); //最多26个字母
auto FindRoot = [&ufs](int x){
while(ufs[x] >= 0)
x = ufs[x];
return x;
};
//第一遍，先把相等的值加到一个集合里
for(auto& str : equations)
{
if(str[1] == '=')
{
int root1 = FindRoot(str[0]-'a');
int root2 = FindRoot(str[3]-'a');
if(root1 != root2)
{
ufs[root1] += ufs[root2];
ufs[root2] = root1;
}
}
}
//第二遍，判断不等的值在不在一个集合里，在就相悖了
for(auto& str : equations)
{
if(str[1] == '!')
{
int root1 = FindRoot(str[0]-'a');
int root2 = FindRoot(str[3]-'a');
if(root1 == root2)
{
return false;
}
}
}
return true;
}
};