summaryrefslogtreecommitdiff
path: root/datastructures/unionFind2.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'datastructures/unionFind2.cpp')
-rw-r--r--datastructures/unionFind2.cpp25
1 files changed, 0 insertions, 25 deletions
diff --git a/datastructures/unionFind2.cpp b/datastructures/unionFind2.cpp
deleted file mode 100644
index 5362c4d..0000000
--- a/datastructures/unionFind2.cpp
+++ /dev/null
@@ -1,25 +0,0 @@
-vector<int> uf;
-
-init(int N) {
- uf.assign(N,-1); //-1 indicates that every subset has size 1
-}
-
-int findSet(int i) {
- if(uf[i] < 0) return i; //If uf[i] < 0 we have reach a root
- uf[i] = findSet(uf[i]); //Path-Compression
- return uf[i];
-}
-
-void linkSets(int i, int j) {
- //Take |uf[i]|, where i must be a root, to get the size
- //of the subset
- if(abs(uf[i]) < abs(uf[j])) { //Union-by-size.
- uf[j] += uf[i]; uf[i] = j;
- } else {
- uf[i] += uf[j]; uf[j] = i;
- }
-}
-
-void unionSets(int i, int j) {
- if(findSet(i) != findSet(j)) linkSets(findSet(i),findSet(j));
-}