模板-并查集DSU

版本1：路径压缩。

struct DSU {
	std::vector<int> fa;
	void init(int n) {
		fa.resize(n + 1);
		std::iota(fa.begin(), fa.end(), 0);
	}
	int leader(int x) {
		while (x != fa[x]) {
			fa[x] = leader(fa[x]);
		}
		return fa[x];
	}
	void join(int x, int y) {
		x = leader(x);
		y = leader(y);
		if (x != y) {
			fa[y] = x;
		}
	}
};

版本2：启发式合并。

struct DSU {
	std::vector<int> fa, sz;
	void init(int n) {
		fa.resize(n + 1);
		std::iota(fa.begin(), fa.end(), 0);
		sz.assign(n + 1, 1);
	}
	int leader(int x) {
		while (x != fa[x]) {
			x = fa[x];
		}
		return x;
	}
	void join(int x, int y) {
		x = leader(x);
		y = leader(y);
		if (x != y) {
			if (sz[x] < sz[y]) {
				std::swap(x, y);
			}
			sz[x] += sz[y];
			fa[y] = x;
		}
	}
};

版本3：用map保存对应关系，适用于标识不是int的场景。

template<typename TYPE>
struct DSU {
	std::map<TYPE,TYPE> fa;
	std::map<TYPE,std::set<TYPE>> contain;
	void add(TYPE x) {
		fa[x] = x;
		contain[x].insert(x);
	}
	void join(TYPE x, TYPE y) {
		x = leader(x);
		y = leader(y);
		if (x != y) {
			if (contain[x].size() < contain[y].size()) {
				std::swap(x, y);
			}
			contain[x].insert(contain[y].begin(), contain[y].end());
			fa[y] = x;
		}
	}
	TYPE leader(TYPE x) {
		return x == fa[x] ? x : fa[x] = get(fa[x]);
	}
};