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する集合に含まれているかなどを確認できたり、いろいろ機能を追加できます。