1 files changed, 79 insertions, 0 deletions
diff --git a/_test/meowpp_DisjointSet.cpp b/_test/meowpp_DisjointSet.cpp
new file mode 100644
index 0000000..b871c4d
--- /dev/null
+++ b/_test/meowpp_DisjointSet.cpp
@@ -0,0 +1,79 @@
+#include "meowpp.h"
+
+#include <vector>
+
+TEST(DisjointSet){
+  int N = 10000000;
+  meow::DisjointSet dsj(N);
+  
+  meow::messagePrintf(1, "merge(0, 1) merge(0, 2) merge(0, 3) ... (N = %d)", N);
+  for(int i = 1; i < N; i++){
+    dsj.merge(0, i);
+  }
+  int root = dsj.root(0);
+  for(int i = 1; i < N; i++){
+    if(root != dsj.root(i)){
+      meow::messagePrintf(-1, "fail");
+      return false;
+    }
+  }
+  meow::messagePrintf(-1, "ok");
+  //
+  
+  dsj.reset(N);
+  meow::messagePrintf(1, "merge(0, 1) merge(1, 2) merge(2, 3) ... (N = %d)", N);
+  for(int i = 1; i < N; i++){
+    dsj.merge(i - 1, i);
+  }
+  root = dsj.root(0);
+  for(int i = 1; i < N; i++){
+    if(root != dsj.root(i)){
+      meow::messagePrintf(-1, "fail");
+      return false;
+    }
+  }
+  meow::messagePrintf(-1, "ok");
+  //
+  
+  int M = 1000;
+  N = 1000000;
+  dsj.reset(N);
+  std::vector<int> used(N, -1);
+  std::vector<int> nums[M];
+  
+  meow::messagePrintf(1, "random test (N = %d)", N);
+  for(int i = 0; i < N / 10; i++){
+    int grp = rand() % M;
+    int who;
+    while(used[who = rand() % N] != -1);
+    nums[grp].push_back(who);
+    used[who] = grp;
+  }
+  meow::messagePrintf(0, "data created");
+  for(int i = 0; i < M; i++){
+    for(int k = 0; k < 100; k++){
+      int j1 = rand() % nums[i].size();
+      int j2 = rand() % nums[i].size();
+      dsj.merge(nums[i][j1], nums[i][j2]);
+    }
+    for(size_t j = 1; j < nums[i].size(); j++){
+      dsj.merge(nums[i][0], nums[i][j]);
+    }
+  }
+  for(int i = 0; i < N; i++){
+    bool ok = false;
+    if(used[i] == -1 && dsj.root(i) == i){
+      ok = true;
+    }else{
+      if(dsj.root(i) == dsj.root(nums[used[i]][0])){
+        ok = true;
+      }
+    }
+    if(!ok){
+      meow::messagePrintf(-1, "fail");
+      return false;
+    }
+  }
+  meow::messagePrintf(-1, "ok");
+  return true;
+};