素集合データ構造
概要
互いに素な集合を扱います．集合のマージと代表元の取得，そしてその一致を根拠にして同じ集合に属するかの判定を行います．
計算量
「データ構造をマージする一般的なテク」と経路圧縮を両方やると，ならしアッカーマン関数の逆関数らしい．
実装
struct uf_tree {
std::vector<int> parent;
int __size;
uf_tree(int size_) : parent(size_, -1), __size(size_) {}
void unite(int x, int y) {
if ((x = find(x)) != (y = find(y))) {
if (parent[y] < parent[x]) std::swap(x, y);
parent[x] += parent[y];
parent[y] = x;
__size--;
}
}
bool is_same(int x, int y) { return find(x) == find(y); }
int find(int x) { return parent[x] < 0 ? x : parent[x] = find(parent[x]); }
int size(int x) { return -parent[find(x)]; }
int size() { return __size; }
};