You do not need a complex tree structure. You need an array called parent. parent[i] stores the parent of node . If parent[i] = i, then is a root (leader).
Initially, everyone is their own leader: parent[i] = i for all . This means separate groups.
As you union elements, you update parent pointers. The array represents the entire forest of groups. Space: . Simple and effective.