#ifndef   DisjointSet_H__
#define   DisjointSet_H__


#include <vector>
#include <cstdlib>

namespace meow{
  //#
  //#=== meow:: *DisjointSet* (C++ class)
  //#==== Description
  //#  `DisjointSet` 是個*輕量級Data Dtructure*, 用來維護一堆互斥集的資訊.
  //#  相關資料可參考
  //#  link:http://www.csie.ntnu.edu.tw/~u91029/DisjointSets.html[演算法筆記]
  //#
  class DisjointSet{
    private:
      size_t              n;
      std::vector<size_t> father;
      std::vector<size_t> depth;
      //
      size_t _root(size_t now);
      size_t _merge(size_t a, size_t b);
    public:
      DisjointSet();
      DisjointSet(size_t _n);
      DisjointSet(DisjointSet const& dsj);

      //#==== Support Methods
      //#
      //#[options="header",width="100%",cols="1>m,3>s,7<,3<,3^,20<",grid="rows"]
      //#|=====================================================================
      //#|Const?|Name | Parameters   | Return_Type| Time_Complexity| Description


      //#|const |root |(size_t `number`) | size_t     | very fast
      //#|回傳 `number` 所在的 *集合的編號* (0~N-1)
      size_t root (size_t a ) const;


      //#|const |size |()              | size_t     | very fast
      //#|回傳 *總集合大小*
      size_t size (         ) const;


      //#|      |reset|(size_t `N`)      | void       | O(N)
      //#| 清空, 並且設定總集合大小為 `N`
      void   reset(size_t _n         );


      //#|      |merge|(size_t `number1`,\size_t `number2`)| size_t  | very fast
      //#| 將 `number1` 所在的集合 跟 `number2` 所在的集合 *合併*,
      //#  並回傳合併後新的集合的編號
      size_t merge(size_t a, size_t b);


      //#|=====================================================================
  };
  //#
  //#[NOTE]
  //#========================================
  //# * *very fast* 表示它算的真的超級快, 可以視為常數時間.
  //# * 預設值所有 `number` 所在的集合的編號就是 `number` 本身, 
  //#    即沒有任兩個數在同一個set裡面
  //#========================================
  //#
  //# '''
}

#include "DisjointSet.hpp"


#endif // DisjointSet_H__