big chnage

1 files changed, 127 insertions, 65 deletions

diff --git a/meowpp/dsa/DisjointSet.h b/meowpp/dsa/DisjointSet.h
index bb777e1..4575835 100644
--- a/meowpp/dsa/DisjointSet.h
+++ b/meowpp/dsa/DisjointSet.h
@@ -1,73 +1,135 @@
 #ifndef   dsa_DisjointSet_H__
 #define   dsa_DisjointSet_H__
 
-#include <cstdlib>
-
 #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);
+  }
+};
 
-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 // dsa_DisjointSet_H__