通俗易懂的C++并查集实现

定义

并查集(Disjoint-Set)的本质是一个森林，即树的集合，但是不需要维护复杂的二叉树/N叉树结构。其使用场景一般用在集合的合并与查询，主要有3个基本 *** 作：

• find_root(x): 查找元素x的根结点，如果
• join_union(x1, x2): 将x1与x2所在集合合并
• is_union(x1,x2): 判断x1与x2是否在同一个集合里

举个例子，很好理解

初始的时候，每个元素都是一个单独的集合，此时find(x) == x, is_union(i,j) == false

现在我们对元素1与元素2做join_union *** 作，即join_union(1,2), 则find(1) == find(2) == 1, is_union(1,2) == true

再进行join_union(1,3), 则元素1，2，3均在一个集合里 is_union(1,2) == is_union(2,3) == is_union(1,3) == true

具体实现

• find_root(x)
  我们用一个哈希表存储每个节点的父节点，如果一个元素是一个单独的集合，则其父节点为自己。 查找一个元素的根结点的时候，我们只需要递归的查询当前节点的父节点，当父节点与当前节点是同一个节点时，递归终止。
  但当一个集合很大的时候，很可能会出现最坏的情况，find_root(x)的时间开销为O(N), 此时我们可以在find_root *** 作中加上一个优化 *** 作，当获取到find_root(x1)的结果为x2后，我们把元素x1的父指针指向x2，以此降低树的高度。该方法叫路径压缩
  

	std::unordered_map<T, T> parent_;
	template <typename T>
	T find_root(const T& x){
		auto parent_it = this->parent_.find(x);
		if (parent_it == this->parent_.end()) {
			this->parent_[x] = x;
			return x;
		}
		return parent_it->second == x ? x : (this->parent_[x] = this->find_root(parent_it->second));
	}

• join_union(x1, x2)
  将元素x1与x2所在的集合合并。首先获取x1与x2各自的根节点r1与r2，然后将其中一个根节点，比如r1，的父指针指向r2即可。这里有个优化点，就是r1与r2应该让哪个做父节点，哪个做子节点。如果不加优化的话，很可能会出现最坏的情况，树的高度等于集合的大小我们可以给每棵树维护一个rank指标，每次都选择rank更大的那棵树作为父节点，让rank小的那棵树成为子节点。我们可以将树的高度作为rank，并且约定rank[i] = height[i] - 1。 该方法叫做按秩合并

	template <typename T>
	void to_union(const T& x1, const T& x2){
		auto x1_parent = this->find_root(x1);
		auto x2_parent = this->find_root(x2);
		if (x1_parent == x2_parent) { return; }
		if (this->rank_[x1_parent] > this->rank_[x2_parent]){
			this->parent_[x2_parent] = x1_parent;
		}else{
			this->parent_[x1_parent] = x2_parent;
			if (this->rank_[x1_parent] >= this->rank_[x2_parent]){ this->rank_[x2_parent]++; }
		}
	}

• is_union(x1,x2):
  判断元素x1与x2是否在一个集合里，只需要判断它们的根节点是否相同即可

	template <typename T>
	bool is_union(const T& x1, const T& x2){
		return this->find_root(x1) == this->find_root(x2);
	}

完整代码实现

#include 

template <typename T>
class DisjSet{
public:
	bool is_union(const T& x1, const T& x2){
		return this->find_root(x1) == this->find_root(x2);
	}

	void to_union(const T& x1, const T& x2){
		auto x1_parent = this->find_root(x1);
		auto x2_parent = this->find_root(x2);
		if (x1_parent == x2_parent) { return; }
		if (this->rank_[x1_parent] > this->rank_[x2_parent]){
			this->parent_[x2_parent] = x1_parent;
		}else{
			this->parent_[x1_parent] = x2_parent;
			if (this->rank_[x1_parent] >= this->rank_[x2_parent]){ this->rank_[x2_parent]++; }
		}
	}
private:
	T find_root(const T& x){
		auto parent_it = this->parent_.find(x);
		if (parent_it == this->parent_.end()) {
			this->parent_[x] = x;
			this->rank_[x] = 0;
			return x;
		}
		return parent_it->second == x ? x : (this->parent_[x] = this->find_root(parent_it->second));
	}
private:
	std::unordered_map<T, T> parent_;
	std::unordered_map<T, size_t> rank_;
};

int main() {

	{
		DisjSet<int> disj_set;
		assert(!disj_set.is_union(1,2));
		disj_set.to_union(1,2);
		assert(disj_set.is_union(1,2));
		disj_set.to_union(2,3);
		assert(disj_set.is_union(1,3));
		assert(disj_set.is_union(2,3));
	}

	{
		DisjSet<std::string> disj_set;
		assert(!disj_set.is_union("a","b"));
		disj_set.to_union("a","b");
		assert(disj_set.is_union("a","b"));
	}
}