DSU.java

/*
 * Author : joney_000[developer.jaswant@gmail.com]
 * Algorithm : Disjoint Set Union O(log n) + path optimization
 * Platform : Codeforces/Leetcode. eg. problem: https://leetcode.com/problems/satisfiability-of-equality-equations/
 */
classDSU {
privateint[] parentOf;
privateint[] depth;
privateintsize;

publicDSU(intsize) {
this.size = size;
this.depth = newint[size + 1];
this.parentOf = newint[size + 1];
clear(size);
 }

// reset 
publicvoidclear(intrange) {
this.size = range;
for (intpos = 1; pos <= range; pos++) {
depth[pos] = 0;
parentOf[pos] = pos;
 }
 }

// Time: O(log n), Auxiliary Space: O(1)
intgetRoot(intnode) {
introot = node;
// finding root
while (root != parentOf[root]) {
root = parentOf[root];
 }
// update chain for new parent
while (node != parentOf[node]) {
intnext = parentOf[node];
parentOf[node] = root;
node = next;
 }
returnroot;
 }

// Time: O(log n), Auxiliary Space: O(1)
voidjoinSet(inta, intb) {
introotA = getRoot(a);
introotB = getRoot(b);
if (rootA == rootB) {
return;
 }
if (depth[rootA] >= depth[rootB]) {
depth[rootA] = Math.max(depth[rootA], 1 + depth[rootB]);
parentOf[rootB] = rootA;
 } else {
depth[rootB] = Math.max(depth[rootB], 1 + depth[rootA]);
parentOf[rootA] = rootB;
 }
 }

intgetNoOfTrees() {
intuniqueRoots = 0;
for (intpos = 1; pos <= size; pos++) {
if (pos == getRoot(pos)) {
uniqueRoots++;// root
 }
 }
returnuniqueRoots;
 }
}