Union-Find木の実装
こちらの習作、というかそのまんま。
http://www.prefield.com/algorithm/container/union_find.html
1: #include <vector>
2: #include <algorithm>
3:
4: struct UnionFind {
5: std::vector<int> data;
6: UnionFind(int size) : data(size, -1) {}
7: bool Union(int x, int y) {
8: if ((x = Root(x)) == (y = Root(y))) return false;
9: if (data[y] < data[x]) std::swap(x, y);
10: data[x] += data[y]; data[y] = x;
11: return true;
12: }
13: bool IsSame(int x, int y) { return Root(x) == Root(y); }
14: int Root(int x) { return data[x] < 0 ? x : data[x] = Root(data[x]); }
15: int Rank(int x) { return -data[Root(x)]; }
16: };
0 件のコメント:
コメントを投稿