高阶数据结构：并查集
本篇主要是介绍并查集的内容：所谓并查集就是一种描述不相交集合的数据结构，即若一个问题涉及多个元素，它们可以划分到不同集合，同属一个集合内的元素等价，不同集合内的元素不等价。
文章目录
- 一、并查集原理
- 二、并查集实现
- 三、并查集应用
一、并查集原理
在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合，开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并，在此过程中要反复用到查询某一个元素归属那个集合的运算，适合于描述这类问题的抽象数据类型称为并查集。
如下图所示：
结论：1、数组下标对应集合中元素的编号。
2、数组中如果为负数，负数代表根，数字代表该集合中元素的个数。
3、数组中如果为非负数，代表该元素双亲在数组中的下标。
如果其中两棵树变成棵树的情况，如下图所示：
通过上面的两张图片可以知道：并查集一般可以解决：
1、查找元素属于哪个集合（沿着数组表示树形关系以上一直找到根（即树中元素为负数的位置）。
2、查看两个元素是否属于同一个集合（沿着数组表示的树形关系往上一直找到树的根，如果根相同表明在同一个集合，否则不在）。
3、将两个集合归并成一个集合（将两个集合中的元素合并，将一个集合名称改成另一个集合的名称） 。
4、集合的个数（遍历数组，数组中元素为负数的个数即为集合的个数）。
二、并查集实现
#include<iostream>
#include<vector>
using namespace std;
class UnionFindSet
{
public:
//初始化：将数组中元素全部设置为1
UnionFindSet(int size)
:_ufs(size, -1)
{}
//给数组元素一个编号，找到该元素所在集合的名称
size_t FindRoot(int x)
{
while (_ufs[x] >= 0)
x = _ufs[x];
return x;
}
//合并两个集合
void Union(int x1, int x2)
{
int root1 = FindRoot(x1);
int root2 = FindRoot(x2);
if (root1 != root2)
{
_ufs[root1] += _ufs[root2];
_ufs[root2] = root1;
}
}
//找出并查集中根的个数
size_t SetCount()
{
size_t count = 0;
for (int i = 0; i < _ufs.size(); i++)
if (_ufs[i] < 0)
count++;
return count;
}
private:
vector<int> _ufs;
};
int main()
{
UnionFindSet ufs(10);
ufs.Union(0, 6);
ufs.Union(0, 7);
ufs.Union(0, 8);
ufs.Union(1, 4);
ufs.Union(1, 9);
ufs.Union(2, 3);
ufs.Union(2, 5);
cout << ufs.SetCount() << endl;
}三、并查集应用
1.省份的数量OJ链接
/*class UnionFindSet
{
public:
UnionFindSet(size_t n)
:_ufs(n,-1)
{}
size_t FindRoot(int x)
{
while(_ufs[x]>=0)
x=_ufs[x];
return x;
}
void Union(int x1,int x2)
{
int root1=FindRoot(x1);
int root2=FindRoot(x2);
if(root1!=root2)
{
_ufs[root1]+=_ufs[root2];
_ufs[root2]=root1;
}
}
size_t SetCount()
{
size_t count=0;
for(int i=0;i<_ufs.size();i++)
if(_ufs[i]<0)
count++;
return count;
}
private:
vector<int> _ufs;
};
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
//手动创建一个并查集
UnionFindSet ufs(isConnected.size());
//如果此时isConnected[i][j]==1说明第i个和第j个城市直接相连，可以认为二者是在同一棵树中
for(int i=0;i<isConnected.size();i++)
for(int j=0;j<isConnected[i].size();j++)
if(isConnected[i][j]==1)
ufs.Union(i,j);
return ufs.SetCount();
}
};*/
class Solution {
public:
size_t FindRoot(vector<int>&_ufs,int x)
{
while(_ufs[x]>=0)
x=_ufs[x];
return x;
}
int findCircleNum(vector<vector<int>>& isConnected) {
vector<int> _ufs(isConnected.size(), -1);
for(int i=0;i<isConnected.size();i++)
{
for(int j=0;j<isConnected[0].size();j++)
{
if(isConnected[i][j]==1)
{
int root1=FindRoot(_ufs,i);
int root2=FindRoot(_ufs,j);
if(root1!=root2)
{
_ufs[root1]=_ufs[root2];
_ufs[root2]=root1;
}
}
}
}
int count=0;
for(int i=0;i<_ufs.size();i++)
if(_ufs[i]<0)
count++;
return count;
}
};2.等式方程的可满足性OJ链接
class Solution {
public:
size_t FindRoot(vector<int>&ufs,int x)
{
while(ufs[x]>=0)
x=ufs[x];
return x;
}
bool equationsPossible(vector<string>& equations) {
vector<int> _ufs(26,-1);
//第一遍是将所有的变量之间相等的放入同一个集合中
for(auto&str:equations)
{
if(str[1]=='=')
{
int root1=FindRoot(_ufs,str[0]-'a');
int root2=FindRoot(_ufs,str[3]-'a');
if(root1!=root2)
{
_ufs[root2]+=_ufs[root1];
_ufs[root1]=root2;
}
}
}
//第二遍是讲不等的变量如果出现在同一个集合中则直接返回false
for(auto&str:equations)
{
if(str[1]=='!')
{
int root1=FindRoot(_ufs,str[0]-'a');
int root2=FindRoot(_ufs,str[3]-'a');
if(root1==root2)
return false;
}
}
return true;
}
};