Optimizing Disjoint Set

This article is inspired by hackerrank problem (https://www.hackerrank.com/challenges/merging-communities/problem). A few weeks ago I tried to solve this hackerrank problem. The algorithm that I used is a disjoint set data structure (https://www.geeksforgeeks.org/union-find/).

This is the source code before the optimization. And for your information, this code get a time limit exceeded.

As we know in disjoint set data structure, if we want to check if 2 nodes are connected in the same graph or not, we need to traverse the parent of the node until the node doesn’t have a parent. This is the code section to do that.

while (parent[source] != 0) {
 source = parent[source];
}
while (parent[destination] != 0) {
 destination = parent[destination];
}

So how to optimize the solution? We can use this code to find the parent.

while (parent[source] != 0) {
 if(parent[parent[source]] != 0)
  parent[source] = parent[parent[source]];
 source = parent[source];
}
while (parent[destination] != 0) {
 if(parent[parent[destination]] != 0)
  parent[destination] = parent[parent[destination]];
 destination = parent[destination];
}

With the current solution, the next time we need to find the parent that has no parent from a node, we only need to iterate 1 time.