The Problem with Naive DSU

Imagine you merge $1-2$, then $2-3$, then $3-4$. Up to $n$. You might end up with a long chain: $1 \to 2 \to 3 \to \cdots \to n$.

If you call find(1), you walk $n-1$ steps. That is $O(n)$ per operation. For $m$ operations, total time is $O(mn)$. This is too slow when $n$ and $m$ are large.

Two optimizations fix this: path compression and union by size/rank. Together they make DSU nearly $O(1)$ per operation.

Space complexity is $O(n)$ for the data structures used.