数据结构---并查集
目录
一、并查集的概念
二、并查集的实现
三、并查集的应用
一、并查集的概念
在一些实际问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-find
set)。
比如：某公司今年校招全国总共招生10人，西安招4人，成都招3人，武汉招3人，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担任队长，负责大家的出行。
虽然这张图画出来是树的形状，但是实际上我们并查集用的数组来存储的。
一趟火车之旅后，每个小分队成员就互相熟悉，称为了一个朋友圈。
在公司工作一段时间后，西安小分队中8号同学与成都小分队1号同学奇迹般的走到了一起，两个
小圈子的学生相互介绍，最后成为了一个小圈子：
现在0集合有7个人，2集合有3个人，总共两个朋友圈。
通过以上例子可知，并查集一般可以解决一下问题：
（1）查找元素属于哪个集合
沿着数组表示树形关系以上一直找到根(即：树中中元素为负数的位置)
（2）查看两个元素是否属于同一个集合
沿着数组表示的树形关系往上一直找到树的根，如果根相同表明在同一个集合，否则不在
（3）将两个集合归并成一个集合
将两个集合中的元素合并
将一个集合名称改成另一个集合的名称
（4）集合的个数
遍历数组，数组中元素为负数的个数即为集合的个数。
并查集其实就是一个帮助我们判断多个元素是否在一个分组的数据结构，他并没有像红黑树这种数据结构的查找、排序功能。
二、并查集的实现
//这个并查集里面啥数据都不存，就存父亲下标或者树的孩子数量
//该数组有几个元素，说明该并查集有几个元素
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)
{
return;
}
else
{
//数据量小的往数据量大的合并
//root1大，root2小
if (abs(_ufs[root1])<abs(_ufs[root2]))
{
swap(root1,root2);
}
//第一棵树数量加上第二棵树的数量
_ufs[root1] += _ufs[root2];
//第二棵树存第一棵树的根节点下标
_ufs[root2] = root1;
}
}
//查找一个值的根(这里的x是下标的意思)
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;
}
//在不在同一颗树（一个集合中）
bool isInSet(int x1,int x2)
{
return FindRoot(x1) == FindRoot(x2);
}
//一共有几棵树
size_t SetSize()
{
size_t size = 0;
for (size_t i=0;i<_ufs.size();i++)
{
if (_ufs[i]<0)
{
size++;
}
}
return size;
}
private:
vector<int> _ufs;
};三、并查集的应用
这就是一道并查集的典型应用题，矩阵就是城市数组竖着横着排列组合而成的，如果i，j位置为1说明两个城市连通，那么我们可以将连通的城市放到一个集合中，不连通的城市单独放到一个集合，最后计算该并查集中有几个集合就知道有几个省份了。
class Solution {
public:
//这里的二维数组，意思是：一维数组都是一个城市，每一个城市下面还存储了一个数组，
//该数组用来表示和其他城市的连接状态
int findCircleNum(vector<vector<int>>& isConnected) {
//用城市的总个数来构造一个并查集，初始时都是-1各自独立
UnionFindSet ufs(isConnected.size());
//遍历每一个城市
for(size_t i=0;i<isConnected.size();i++)
{
//在每一个城市中，找到自己的连通信息，如果自己信息数组【j】为1，则说明自己城市和j城市连通，则放入一个树中
for(size_t j=0;j<isConnected[i].size();j++)
{
//如果两个城市直接相互连同，则放到一棵树中
if(isConnected[i][j]==1)
{
ufs.Union(i,j);
}
}
}
return ufs.SetSize();
}
};
因为题目中限制了字母只会在a-z中出现，而英文字母天然在ascii中就是有序存放的，所以我们知道他们的一一映射关系，即可创建一个26大小的并查集，其中[0]对应a，[25]对应z。
在使用字母找到映射的下标的时候，只需要用该字母的ascii码-'a'即可对应上0-25下标。
class Solution {
public:
bool equationsPossible(vector<string>& equations) {
//因为题目说明字母只有小写的a-z，而他们在ascii中又天然有序，所以创建一个26大小的并查集
UnionFindSet ufs(26);
//第一次遍历vector<string>将题目中说相等的放到一个集合
for(auto& str:equations)
{
if(str[1]=='=')
{
//如果本身不在一个集合，则合并到一个集合中
int root1=ufs.FindRoot(str[0]-'a');
int root2=ufs.FindRoot(str[3]-'a');
if(root1!=root2)
{
ufs.Union(str[0]-'a',str[3]-'a');
}
}
}
//第二次遍历，如果发现不相等之前被我们放到一个集合，则错误。全部没有则正确
for(auto& str:equations)
{
if(str[1]=='!')
{
int root1=ufs.FindRoot(str[0]-'a');
int root2=ufs.FindRoot(str[3]-'a');
if(root1==root2)
{
return false;
}
}
}
return true;
}
};