Improvement 2: Path Compression
After computing the root of $p$, 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 $I$, $F$, $B$ until we get to $A$, 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.