Union Find Disjoint Set Data Structure in DSA C

Mental Model

Union Find keeps track of groups of connected items by linking them under a single leader. It helps quickly find if two items belong to the same group.

Analogy: Imagine a classroom where students form friend groups. Each group has a leader. If two students are friends, they share the same leader. Union Find helps find the leader of any student and join two groups by choosing one leader.

0 1 2 3 4 5 6 7 8 9
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑
Each number is alone, leader points to itself:
0 -> 0
1 -> 1
2 -> 2
3 -> 3
4 -> 4
5 -> 5
6 -> 6
7 -> 7
8 -> 8
9 -> 9

Dry Run Walkthrough

Input: Start with 5 elements: 0,1,2,3,4 all separate. Perform union(0,1), union(1,2), union(3,4), then check if 0 and 2 are connected.

Goal: Show how union merges groups and find checks if two elements share the same leader.

Step 1: Initialize each element as its own leader

0 -> 0
1 -> 1
2 -> 2
3 -> 3
4 -> 4

Why: Start with all elements separate, each is leader of itself

Step 2: Union 0 and 1: make leader of 1 point to leader of 0

0 -> 0
1 -> 0
2 -> 2
3 -> 3
4 -> 4

Why: Connect 0 and 1 by linking 1 under 0's leader

Step 3: Union 1 and 2: find leaders of 1 and 2, link leader of 2 to leader of 0

0 -> 0
1 -> 0
2 -> 0
3 -> 3
4 -> 4

Why: 2 joins the group led by 0 through 1

Step 4: Union 3 and 4: make leader of 4 point to leader of 3

0 -> 0
1 -> 0
2 -> 0
3 -> 3
4 -> 3

Why: Connect 3 and 4 as a separate group

Step 5: Find if 0 and 2 are connected: find leaders of both

0 -> 0
1 -> 0
2 -> 0
3 -> 3
4 -> 3

Why: Both 0 and 2 have leader 0, so they are connected

Result:

0 -> 0
1 -> 0
2 -> 0
3 -> 3
4 -> 3
Answer: 0 and 2 are connected (same leader)

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

#define SIZE 5

int parent[SIZE];

// Find leader of element x with path compression
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // path compression
    }
    return parent[x];
}

// Union two sets by linking leaders
void union_sets(int a, int b) {
    int leaderA = find(a);
    int leaderB = find(b);
    if (leaderA != leaderB) {
        parent[leaderB] = leaderA; // link leaderB under leaderA
    }
}

int main() {
    // Initialize each element as its own leader
    for (int i = 0; i < SIZE; i++) {
        parent[i] = i;
    }

    union_sets(0, 1);
    union_sets(1, 2);
    union_sets(3, 4);

    // Check if 0 and 2 are connected
    if (find(0) == find(2)) {
        printf("0 and 2 are connected\n");
    } else {
        printf("0 and 2 are NOT connected\n");
    }

    // Print parent array to show structure
    printf("Parent array:\n");
    for (int i = 0; i < SIZE; i++) {
        printf("%d -> %d\n", i, parent[i]);
    }

    return 0;
}

if (parent[x] != x) { parent[x] = find(parent[x]); }

Recursively find leader and compress path for faster future lookups

int leaderA = find(a); int leaderB = find(b);

Find leaders of both elements before union

if (leaderA != leaderB) { parent[leaderB] = leaderA; }

Link one leader under the other to merge sets

for (int i = 0; i < SIZE; i++) { parent[i] = i; }

Initialize each element as its own leader

Output

0 and 2 are connected

Parent array:

0 -> 0

1 -> 0

2 -> 0

3 -> 3

4 -> 3

Complexity Analysis

Time: O(α(n)) per operation, where α is inverse Ackermann function, almost constant because path compression flattens trees

Space: O(n) for storing parent array of size n

vs Alternative: Naive union without path compression can be O(n) per find, so this is much faster for many operations

Edge Cases

Union on elements already in the same set

No change occurs because leaders are same, avoiding cycles

DSA C

if (leaderA != leaderB) { parent[leaderB] = leaderA; }

Find on element that is its own leader

Returns element itself immediately, no recursion

DSA C

if (parent[x] != x) { ... }

Union on invalid element index (out of range)

Undefined behavior, code assumes valid input

DSA C

No explicit guard; input must be valid

When to Use This Pattern

When a problem asks to group items and quickly check if two items belong to the same group, use Union Find because it efficiently merges and finds group leaders.

Common Mistakes

Mistake: Not using path compression in find, causing slow repeated lookups
Fix: Add path compression by setting parent[x] = find(parent[x]) during find

Mistake: Linking leaders incorrectly causing cycles or wrong groups
Fix: Always link leader of one set to leader of the other after finding leaders

Summary

It keeps track of connected groups by linking elements under a single leader.

Use it when you need to quickly merge groups and check if two elements are connected.

The key is to find leaders and link them, using path compression to speed up future lookups.