在一些应用问题中,需要将n个不同的元素划分成一些不相交的集合。开始时,每个元素自成一个单元素集合,然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-findset)。 并查集一般可以解决一下问题:
#include<iostream>
#include<vector>
using namespace std;
class UnionFindSet{
public:
UnionFindSet(size_t size)//构造函数,初始化数组大小
:_a(size,-1){
}
int FindRoot(int x){//查找根节点
while (_a[x] >= 0){//循环寻找节点小于0的节点为根
x = _a[x];
}
return x;
}
bool Union(int x1, int x2){//合并两个节点
int root1 = FindRoot(x1);//查找两个节点的根节点
int root2 = FindRoot(x2);
if (root1 == root2)//根节点相同,说明在一根树上
return false;
_a[root1] += _a[root2];//将root1根节点的值变为root2的值和root1值的和,也就是负的子节点个数
_a[root2] = root1;//将root2的值赋予root1节点中
return true;
}
size_t Count(){//根节点的个数,即节点值小于0的个数
int count = 0;
for (auto e : _a){
if (e < 0)
count++;
}
return count;
}
private:
vector<int> _a;
};