The Parent Array

You do not need a complex tree structure. You need an array called parent. parent[i] stores the parent of node $i$. If parent[i] = i, then $i$ is a root (leader).

Initially, everyone is their own leader: parent[i] = i for all $i$. This means $n$ separate groups.

As you union elements, you update parent pointers. The array represents the entire forest of groups. Space: $O(n)$. Simple and effective.