Union Find Disjoint Set Data Structure in DSA C - Build from Scratch

Union Find Disjoint Set Data Structure

📖 Scenario: Imagine you have a group of friends, and you want to know if two friends are in the same friend circle. A friend circle means everyone is connected directly or through other friends. We will use a Union Find Disjoint Set data structure to keep track of these friend circles.

🎯 Goal: You will build a simple Union Find Disjoint Set in C that can join two friend circles and check if two friends belong to the same circle.

📋 What You'll Learn

Create an array called parent to represent each friend's parent in the set

Create an array called rank to keep track of the tree height for optimization

Write a function find that returns the root parent of a friend with path compression

Write a function union_sets that joins two friend circles using rank to keep trees short

Write code to check if two friends are in the same friend circle using find

💡 Why This Matters

🌍 Real World

Union Find is used in social networks to find connected groups, in network connectivity, and in clustering problems.

💼 Career

Understanding Union Find helps in solving problems related to grouping, connectivity, and efficient merging in software engineering and competitive programming.

1

Create the parent and rank arrays

Create two arrays called parent and rank of size 5. Initialize parent so each friend is their own parent (0 to 4), and initialize rank with all zeros.

DSA C

# Create arrays parent and rank with initial values
# Your code here

Hint

Use a for loop from 0 to 4 to set parent[i] = i and rank[i] = 0.

2

Write the find function with path compression

Write a function called find that takes an integer x and returns the root parent of x. Use path compression by setting parent[x] to the root parent during the search.

DSA C

#include 

int parent[5];
int rank[5];

int find(int x) {
    // Write find function with path compression
    // Your code here
}

int main() {
    for (int i = 0; i < 5; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
    return 0;
}

Hint

Check if parent[x] is not x. If so, call find recursively and update parent[x].

3

Write the union_sets function to join two sets

Write a function called union_sets that takes two integers a and b. Find their root parents using find. If they are different, attach the smaller rank tree under the bigger rank tree. If ranks are equal, attach b under a and increase rank[a] by 1.

DSA C

#include 

int parent[5];
int rank[5];

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

void union_sets(int a, int b) {
    // Write union_sets function to join sets
    // Your code here
}

int main() {
    for (int i = 0; i < 5; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
    return 0;
}

Hint

Use find on both a and b. Compare ranks and attach the smaller tree under the bigger one. If equal, attach b under a and increase rank[a].

4

Check if two friends are in the same set and print result

In main, use union_sets to join friends 0 and 1, and friends 1 and 2. Then check if friends 0 and 2 are in the same set by comparing find(0) and find(2). Print "Yes" if they are in the same set, otherwise print "No".

DSA C

#include 

int parent[5];
int rank[5];

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

void union_sets(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) {
        if (rank[a] < rank[b]) {
            parent[a] = b;
        } else if (rank[b] < rank[a]) {
            parent[b] = a;
        } else {
            parent[b] = a;
            rank[a]++;
        }
    }
}

int main() {
    for (int i = 0; i < 5; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
    // Use union_sets to join friends 0 and 1, and 1 and 2
    // Check if 0 and 2 are in the same set and print "Yes" or "No"
    // Your code here
    return 0;
}

Hint

Call union_sets(0, 1) and union_sets(1, 2). Then compare find(0) and find(2). Print "Yes" if equal, else "No".

Practice

1. What is the main purpose of the Union Find Disjoint Set data structure?

easy

A. To sort elements in ascending order

B. To efficiently track and merge groups of connected elements

C. To store key-value pairs for fast lookup

D. To implement a queue with priority

Solution

1. Step 1: Understand the role of Union Find

   The Union Find data structure is designed to keep track of which elements belong to which groups or sets, especially when these groups merge.

2. Step 2: Compare with other data structures

   Sorting, key-value storage, and priority queues serve different purposes unrelated to grouping connected components.

3. Final Answer:

   To efficiently track and merge groups of connected elements -> Option B

4. Quick Check:

   Union Find = track and merge groups [OK]

Hint: Union Find = manage connected groups fast [OK]

Common Mistakes:

• Confusing Union Find with sorting algorithms
• Thinking it stores key-value pairs
• Assuming it manages priority queues

2. Which of the following is the correct way to initialize a Union Find parent array for n elements in C?

easy

A. int parent[n]; for(int i=0; i

B. int parent[n]; for(int i=0; i

C. int parent[n]; for(int i=0; i

D. int parent[n]; for(int i=0; i

Solution

1. Step 1: Understand initialization of Union Find

   Each element starts as its own parent, so parent[i] = i for all i from 0 to n-1.

2. Step 2: Check each option

   int parent[n]; for(int i=0; i

3. Final Answer:

   int parent[n]; for(int i=0; i -> Option A

4. Quick Check:

   Initialize parent[i] = i [OK]

Hint: Parent array starts with self indices [OK]

Common Mistakes:

• Setting all parents to zero
• Using -1 as parent without meaning
• Assigning parent to n (out of range)

3. Consider the following C code using Union Find for 5 elements (0 to 4):

int parent[5];
for(int i=0; i<5; i++) parent[i] = i;

// Union operations
union_set(parent, 0, 1);
union_set(parent, 1, 2);
union_set(parent, 3, 4);

// Find operations
int a = find_set(parent, 2);
int b = find_set(parent, 4);

printf("%d %d", a, b);

Assuming union_set merges sets and find_set returns the root parent, what is the printed output?

medium

A. 0 3

B. 1 3

C. 2 4

D. 0 4

Solution

1. Step 1: Trace union operations

   Initially, parent[i] = i for i=0..4.
   union_set(0,1) merges sets containing 0 and 1, root becomes 0.
   union_set(1,2) merges sets containing 1 and 2, root is 0 (since 1's root is 0).
   union_set(3,4) merges sets containing 3 and 4, root becomes 3.

2. Step 2: Trace find operations

   find_set(2) returns root of 2, which is 0.
   find_set(4) returns root of 4, which is 3.

3. Final Answer:

   0 3 -> Option A

4. Quick Check:

   Roots after unions: 2->0, 4->3 [OK]

Hint: Follow union roots to find final parents [OK]

Common Mistakes:

• Assuming find_set returns the element itself
• Not updating roots after unions
• Mixing up which element is root

4. The following C code attempts to implement union_set but has a bug:

void union_set(int parent[], int a, int b) {
    int rootA = find_set(parent, a);
    int rootB = find_set(parent, b);
    if (rootA != rootB) {
        parent[a] = rootB;
    }
}

What is the bug in this code?

medium

A. It should assign parent[rootB] = rootA instead

B. It does not check if rootA equals rootB before union

C. It assigns parent[a] instead of parent[rootA], breaking the set structure

D. It uses find_set incorrectly by passing wrong parameters

Solution

1. Step 1: Analyze union assignment

   The union should link the root of one set to the root of the other.
   Assigning parent[a] = rootB is wrong because 'a' may not be a root.

2. Step 2: Correct union assignment

   It should assign parent[rootA] = rootB to merge sets properly.
   This maintains the tree structure of the disjoint sets.

3. Final Answer:

   It assigns parent[a] instead of parent[rootA], breaking the set structure -> Option C

4. Quick Check:

   Union must link roots, not elements [OK]

Hint: Always link root parents in union [OK]

Common Mistakes:

• Assigning parent of non-root element
• Skipping root equality check
• Confusing parameters in find_set

5. You have 7 elements (0 to 6) initially separate. After these union operations:

union_set(parent, 0, 1);
union_set(parent, 1, 2);
union_set(parent, 3, 4);
union_set(parent, 5, 6);
union_set(parent, 2, 5);

How many distinct sets remain?

hard

A. 5

B. 4

C. 3

D. 2

Solution

1. Step 1: Track unions step-by-step

   Initially: 7 sets: {0}, {1}, {2}, {3}, {4}, {5}, {6}
   union(0,1): {0,1}, {2}, {3}, {4}, {5}, {6}
   union(1,2): {0,1,2}, {3}, {4}, {5}, {6}
   union(3,4): {0,1,2}, {3,4}, {5}, {6}
   union(5,6): {0,1,2}, {3,4}, {5,6}
   union(2,5): merges sets {0,1,2} and {5,6} into {0,1,2,5,6}, {3,4}

2. Step 2: Count remaining sets

   Remaining sets are {0,1,2,5,6} and {3,4}.
   Total distinct sets = 2.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Count sets after unions = 2 [OK]

Hint: Count merged groups carefully after each union [OK]

Common Mistakes:

• Forgetting last union merges two sets
• Counting elements instead of sets
• Assuming all unions merge all sets