From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 27 Jun 2022 17:19:28 +0200 Subject: updated tcr --- datastructures/unionFind2.cpp | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+) create mode 100644 datastructures/unionFind2.cpp (limited to 'datastructures/unionFind2.cpp') diff --git a/datastructures/unionFind2.cpp b/datastructures/unionFind2.cpp new file mode 100644 index 0000000..225ecee --- /dev/null +++ b/datastructures/unionFind2.cpp @@ -0,0 +1,27 @@ +vector 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)); +} + + -- cgit v1.2.3