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?