[C++知识库]并查集C++实现

先贴代码（防忘，有空再写理解）

#include <iostream>
#include <vector>

using namespace std;

class Disjoint_set {
public:
	vector<int> parent;
	vector<int> rank;
	Disjoint_set(const int & n) {
		parent = vector<int>(n, 0);
		rank = vector<int>(n, 0);
		for(int i = 0; i < n; i++)
			parent[i] = i;
	}
	
	int find_parent(const int & x) {
		if(parent[x] == x)
			return x;
		else
			return find_parent(parent[x]);
	}
	
	bool merge(const int & x, const int & y) {
		int x_root = find_parent(x);
		int y_root = find_parent(y);
		
		if(x_root == y_root)
			return false;
		else if(x_root != y_root && rank[x_root] > rank[y_root]) 
			parent[y_root] = x_root;
		else if(x_root != y_root && rank[x_root] < rank[y_root])
			parent[x_root] = y_root;
		else {
			parent[y_root] = x_root;
			rank[x_root]++;
		}
		return true;
	}
};