init

1 files changed, 52 insertions, 0 deletions

diff --git a/meowpp/dsa/DisjointSet.hpp b/meowpp/dsa/DisjointSet.hpp
new file mode 100644
index 0000000..3b66626
--- /dev/null
+++ b/meowpp/dsa/DisjointSet.hpp
@@ -0,0 +1,52 @@
+#include <vector>
+#include <cstdlib>
+
+namespace meow{
+  inline size_t DisjointSet::_root(size_t now){
+    if(father[now] == now) return now;
+    return (father[now] = _root(father[now]));
+  }
+  inline size_t DisjointSet::_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;
+    }
+  }
+  //
+  inline DisjointSet::DisjointSet(): n(0){ }
+  inline DisjointSet::DisjointSet(size_t _n): n(0){
+    reset(_n);
+  }
+  inline DisjointSet::DisjointSet(DisjointSet const& dsj){
+    n      = dsj.n;
+    father = dsj.father;
+    depth  = dsj.depth;
+  }
+  //
+  inline size_t DisjointSet::root(size_t a) const{
+    return ((DisjointSet*)this)->_root(a);
+  }
+  inline size_t DisjointSet::size() const{ return n; }
+  //
+  inline void DisjointSet::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;
+    }
+  }
+  inline size_t DisjointSet::merge(size_t a, size_t b){
+    return _merge(a, b);
+  }
+}