マージテクUF

todoリストに載っていたので。

struct mergeUF { //O(logn^2)
	int n;
	vector<set<int>> g;
	vector<int> gat;
	void init(int mx) {
		n = mx;
		g.resize(n); gat.resize(n);
		rep(i, 0, n) {
			g[i].insert(i);
			gat[i] = i;
		}
	}

	mergeUF(int mx = 0) { init(mx); }

	void unite(int x, int y) {
		int a = gat[x], b = gat[y];
		if(a == b) return;
		if(sz(g[a]) > sz(g[b])) swap(a, b);

		for(int s : g[a]) {
			gat[s] = b;
			g[b].insert(s);
		}
		g[a].clear();
	}

	bool same(int x, int y) { return gat[x] == gat[y]; }
	void show() {
		rep(i, 0, n) debug(i, vi(all(g[i])));
		debug(gat);
	}
};

setで実装している分遅いですが、mergeされる集合の要素が、mergeする集合に含まれているかなどを確認できたり、いろいろ機能を追加できます。