6.14.2011

C++: Union-Find data structure

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: };
rank がアンダーフローしたらどうなる?

0 件のコメント:

コメントを投稿