一、原理
在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。
开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。
在此过程中要反复用到查询某一个元素归属于那个集合的运算。
适合于描述这类问题的抽象数据类型称为并查集(union-find set)。
例子：假设有一个班级中有10个学生，每个学生最初属于一个独立的集合。
随着学生之间的互动，他们可能会形成新的集合或加入到已有的集合中。
例如：
-
学生A和学生B成为朋友，他们属于同一个集合。
-
学生C和学生D也成为朋友，他们属于另一个集合。
-
学生A和学生C互动，他们所在的集合合并。
结论：
-
数组的下标对应集合中元素的编号
-
数组中如果为负数，负号代表根，数字代表该集合中元素个数
-
数组中如果为非负数，代表该元素双亲在数组中的下标
二、作用
并查集一般可以解决一下问题：
-
查找元素属于哪个集合
沿着数组表示树形关系以上一直找到根(即：树中中元素为负数的位置)
-
查看两个元素是否属于同一个集合
沿着数组表示的树形关系往上一直找到树的根，如果根相同表明在同一个集合，否则不在
-
将两个集合归并成一个集合
将两个集合中的元素合并，将一个集合名称改成另一个集合的名称
-
集合的个数
遍历数组，数组中元素为负数的个数即为集合的个数。
三、实现
UnionFindSet.h
#pragma once
#include<vector>
#include<map>
//template<class T>
//class UnionFindSet
//{
//public:
// UnionFindSet(const T* a, size_t n)
// {
// for (size_t i = 0; i < n; i++)
// {
// _a.push_back(a[i]);
// _indexMap[a[i]] = i;
// }
// }
//private:
// vector<T> _a; //编号找人
// map<T, int> _indexMap;//人找编号
//};
// 0 | 1 | 2
//6 7 8 | 4 9 | 3 5
// 0 1 2 3 4 5 6 7 8 9
// -4 -3 -3 2 1 2 0 0 0 1
// -7 0 -3 2 1 2 0 0 0 1
//1. 数组的下标对应集合中元素的编号
//2. 数组中如果为负数，负号代表根，数字代表该集合中元素个数
//3. 数组中如果为非负数，代表该元素双亲在数组中的下标
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;
}
if (abs(_ufs[root1]<abs(_ufs[root2])))
{
swap(root1, root2);
}
//2合并进1中
_ufs[root1] += _ufs[root2];
_ufs[root2] = root1;
}
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 InSet(int x1, int x2)
{
return Findroot(x1) == Findroot(x2);
}
size_t SetSize()
{
size_t size;
for (size_t i = 0; i < _ufs.size(); i++)
{
if (_ufs[i] < 0)
{
++size;
}
}
return size;
}
private:
vector<int> _ufs;
};
void TestUnionFindSet()
{
UnionFindSet ufs(10);
ufs.Union(8, 9);
ufs.Union(7, 8);
ufs.Union(6, 7);
ufs.Union(5, 6);
ufs.Union(4, 5);
ufs.Findroot(9);
}四、应用
1.LRC 116.省份数量
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
vector<int> ufs(isConnected.size(),-1);
auto findRoot=[&ufs](int x)
{
while(ufs[x]>=0)
{
x=ufs[x];
}
return x;
};
for(size_t i=0;i<isConnected.size();i++)
{
for(size_t j=0;j<isConnected[i].size();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 n=0;
for(auto e:ufs)
{
if(e<0)
{
++n;
}
}
return n;
}
};2. 990.等式方程的可满足性
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 &str:equations)
{
if(str[1]=='=')
{
int r1=findroot(str[0]-'a');
int r2=findroot(str[3]-'a');
if(r1!=r2)
{
ufs[r1]+=ufs[r2];
ufs[r2]=r1;
}
}
}
//第二遍 看不相等的在不在一个集合 在就相勃了
//返回false
for(auto &str:equations)
{
if(str[1]=='!')
{
int r1=findroot(str[0]-'a');
int r2=findroot(str[3]-'a');
if(r1==r2)
{
return false;
}
}
}
return true;
}
};