#ifndef   dsa_DisjointSet_H__
#define   dsa_DisjointSet_H__

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

namespace meow {
/*!
 * @brief 用來維護一堆互斥集的資訊
 *
 * DisjointSet 是個 \b 輕量級Data \b Dtructure, 用來維護一堆互斥集的資訊. \n
 * 相關資料可參考
 * <a href="http://www.csie.ntnu.edu.tw/~u91029/DisjointSets.html">
 *   演算法筆記
 * </a> 
 *
 * @note
 *    - 時間複雜度 \b 非常快 表示它真的算的超級快, 可以視為常數時間
 *    - 預設值所有 \a number 所在的集合的編號就是 \a number 本身, 
 *      即沒有任兩個數在同一個set裡面
 *
 * @author cat_leopard
 */
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:
  /*!
   *@brief constructor
   */
  DisjointSet(): n_(0) {
  }

  /*!
   *@brief constructor
   *
   *@param [in] n elements數
   */
  DisjointSet(size_t n) {
    reset(n);
  }

  /*!
   *@brief constructor
   *
   *將另一個 \c DisjointSet 原封不動的複製過來
   *
   *@param [in] dsj 另一個 \c DisjointSet
   */
  DisjointSet(DisjointSet const& dsj):
  n_(dsj.n_), father_(dsj.father_), depth_(dsj.depth_) {
  }

  /*!
   *@brief 回傳指定的number所在的 \b 集合的編號
   *
   *時間複雜度 \b 超級快
   *
   *@param [in] a 指定的number
   *@return 集合的編號
   */
  size_t root(size_t a) const {
    return ((DisjointSet*)this)->root_(a);
  }


  /*!
   *@brief 回傳總element數
   *
   *@return 總element數
   */
  size_t size() const {
    return n_;
  }

  /*!
   *@brief 重設
   *
   *清空, 並且設定總集合大小為 \a n
   *
   *@param [in] n 重新設定的集合大小 \a n
   *@return 無
   */
  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;
    }
  }

  /*!
   * @brief 合併
   *
   * 將 \a number1 所在的集合 跟 \b number2 所在的集合 \b 合併,
   * 並回傳合併後新的集合的編號. \n
   * 時間複雜度\b 非常快 
   *
   * @param [in] a 即上述\a number1
   * @param [in] b 即上述\a number2
   * @return 新的編號
   */
  size_t merge(size_t a, size_t b) {
    return merge_(a, b);
  }
};

}

#endif // dsa_DisjointSet_H__