DisjointSet.h

Go to the documentation of this file.

#ifndef   dsa_DisjointSet_H__
#define   dsa_DisjointSet_H__

#include <vector>
#include <cstdlib>
#include <cstdio>

namespace meow {
class DisjointSet {
private:
  size_t              n_;
  std::vector<size_t> father_;
  std::vector<size_t> depth_;
  //
  size_t root_(size_t now) {
    if (father_[now] == now) return now;
    return (father_[now] = root_(father_[now]));
  }

  size_t merge_(size_t a, size_t b) {
    a = root_(a);
    b = root_(b);
    if (a == b) return a;
    if (depth_[a] > depth_[b]) {
      father_[b] = a;
      return a;
    }
    else {
      father_[a] = b;
      if (depth_[a] == depth_[b]) depth_[b]++;
      return b;
    }
  }
public:
  DisjointSet(): n_(0) {
  }

  DisjointSet(size_t n) {
    reset(n);
  }

  DisjointSet(DisjointSet const& dsj):
  n_(dsj.n_), father_(dsj.father_), depth_(dsj.depth_) {
  }

  size_t root(size_t a) const {
    return ((DisjointSet*)this)->root_(a);
  }


  size_t size() const {
    return n_;
  }

  void reset(size_t n) {
    n_ = n;
    father_.resize(n);
    depth_ .resize(n);
    for (size_t i = 0; i < n; i++) {
      father_[i] = i;
      depth_ [i] = 1;
    }
  }

  size_t merge(size_t a, size_t b) {
    return merge_(a, b);
  }
};

} // meow

#endif // dsa_DisjointSet_H__