Common Mistakes

• Forgetting path compression: Without optimization, Union Find degrades to $O(n)$ per operation. Always compress paths.
• Union without finding roots first: Union the roots, not the original elements.

Find(x) != x in general.

• Not tracking component count correctly: Decrement count on successful union (when roots differ), not on every union call.
• Using element value instead of index: Union Find works on indices. Map elements to indices if needed.