并查集的原理及实现

#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;
};