[Solved] Path Compression , How does this code is path compression?


id[i] = id[id[i]];

This line is the path compression. id[i] is the parent of node i. Hence, this line re-links node i to its grand-parent. Therefore, it skips the parent. Then, the same happens to the grand-parent and so on. This flattens the tree.

Here is a visualization of this step:

1                    1
^                   / \
|     root(3)      /   \
2    -------->   2       3
^
|
3

solved Path Compression , How does this code is path compression?