Improvement 2: Path Compression
After computing the root of , set the ID of each examined node to point to that root.
For example, consider the following tree:
Assume we perform find(J) operation. On our way to find the root, we would pass through , , until we get to , the root.
We could set all these vertices to directly point to the root, so the tree becomes shallower:
The heuristic described above is known as path compression.