🔗 Disjoint Sets / Union-Find

After completing this level, you should be able to:

• Explain a partition and the representative of a disjoint set.
• Perform Make-Set, Find and Union operations.
• Represent a collection of sets as a forest of rooted trees.
• Apply path compression during Find.
• Apply union by rank and union by size.
• Use Union-Find to solve connectivity, cycle-detection and Kruskal problems.
• Justify the nearly constant amortized complexity of optimized operations.

A disjoint-set data structure, also called Union-Find or DSU, maintains a collection of sets that do not share elements.

One element in each set is chosen as its representative. Two elements belong to the same set exactly when their representatives are equal.

Each set is stored as a rooted tree. All the trees together form a forest. An array named parent stores the immediate parent of every element.

• A root satisfies parent[root] == root.
• The root is used as the representative of the entire set.
• The logical set is independent of which particular element becomes its representative.

The basic Find operation moves upward until it reaches a self-parent root.

int findSet(int x) {
    if (parent[x] == x)
        return x;
    return findSet(parent[x]);
}

int findSet(int x) {
    while (parent[x] != x)
        x = parent[x];
    return x;
}

void unionSets(int a, int b) {
    int rootA = findSet(a);
    int rootB = findSet(b);

    if (rootA != rootB)
        parent[rootB] = rootA;
}

Start with elements 0 to 6. Every element is initially its own representative.

The program supports Union, Find and Connected queries using path compression and union by rank.

#include <stdio.h>

#define MAX 1000

int parent[MAX];
int rankValue[MAX];

void makeSet(int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        rankValue[i] = 0;
    }
}

int findSet(int x) {
    if (parent[x] != x)
        parent[x] = findSet(parent[x]);
    return parent[x];
}

void unionSets(int a, int b) {
    int rootA = findSet(a);
    int rootB = findSet(b);

    if (rootA == rootB)
        return;

    if (rankValue[rootA] < rankValue[rootB]) {
        parent[rootA] = rootB;
    } else if (rankValue[rootA] > rankValue[rootB]) {
        parent[rootB] = rootA;
    } else {
        parent[rootB] = rootA;
        rankValue[rootA]++;
    }
}

int main(void) {
    int n, q;
    scanf("%d %d", &n, &q);

    if (n < 1 || n > MAX)
        return 0;

    makeSet(n);

    while (q--) {
        int type, a, b;
        scanf("%d", &type);

        if (type == 1) {
            scanf("%d %d", &a, &b);
            unionSets(a, b);
        } else if (type == 2) {
            scanf("%d", &a);
            printf("Representative of %d: %d\n", a, findSet(a));
        } else if (type == 3) {
            scanf("%d %d", &a, &b);
            if (findSet(a) == findSet(b))
                printf("Connected\n");
            else
                printf("Not Connected\n");
        }
    }

    return 0;
}

8 9
1 0 1
1 2 3
1 1 3
3 0 3
2 3
1 4 5
1 5 6
3 4 6
3 0 7

Connected
Representative of 3: 0
Connected
Not Connected

Follow the sample input one operation at a time and observe how the parent and rank arrays change.

makeSet(n);
int rootA = findSet(a);
int rootB = findSet(b);
if (rootA == rootB) return;
if (rankValue[rootA] < rankValue[rootB])
    parent[rootA] = rootB;
else if (rankValue[rootA] > rankValue[rootB])
    parent[rootB] = rootA;
else { parent[rootB] = rootA;
       rankValue[rootA]++; }
parent[x] = findSet(parent[x]);
printf(...);

—

Process edges one by one. For an edge (u, v):

• Union-Find answers connectivity under edge additions efficiently, but basic DSU does not support deletion easily.
• Path compression changes parent links without changing set membership.
• Rank is an upper-bound style balancing measure, not necessarily the current exact height.
• Counting roots after all operations gives the number of connected components.
• Kruskal’s algorithm uses DSU to reject edges that would create cycles.

• Disjoint Set Union maintains a partition of elements into non-overlapping groups.
• Make-Set creates a singleton; Find returns a representative; Union merges two sets.
• A parent array represents each set as a rooted tree.
• Union by rank or size avoids unnecessarily tall trees.
• Path compression connects visited nodes closer to the root.
• With both optimizations, operations take O(α(n)) amortized time.
• DSU is central to connectivity, undirected-cycle detection and Kruskal’s algorithm.