Path Compression in Union Find in DSA C - Build from Scratch

Path Compression in Union Find

📖 Scenario: Imagine you are managing a social network where people form friend groups. You want to quickly find out if two people are in the same friend group and efficiently merge groups when new friendships form.

🎯 Goal: You will build a Union Find data structure with path compression to quickly find the leader (representative) of each friend group. This helps speed up queries about group membership.

📋 What You'll Learn

Create an array called parent to represent each person's group leader.

Create an integer variable n for the number of people.

Write a function find that uses path compression to find the leader of a person.

Write a function union_sets to merge two groups by connecting their leaders.

Print the parent array after some union operations to show the final group leaders.

💡 Why This Matters

🌍 Real World

Union Find with path compression is used in social networks, network connectivity, and clustering to quickly find connected components.

💼 Career

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

1

Create the parent array for 5 people

Create an integer variable n and set it to 5. Then create an integer array called parent of size n. Initialize each element of parent so that parent[i] = i for i from 0 to n-1.

DSA C

int n = 5;
int parent[5];
// Initialize parent array so that parent[i] = i
// Your code here

Hint

Use a for loop from 0 to n-1 and set parent[i] to i.

2

Write the find function with path compression

Write a function called find that takes an integer x and returns the leader of x. Use path compression by setting parent[x] to the result of find(parent[x]) when x is not its own parent.

DSA C

int find(int x) {
    // Your code here
}

Hint

Check if x is its own parent. If not, update parent[x] by calling find recursively.

3

Write the union_sets function to merge two groups

Write a function called union_sets that takes two integers a and b. Find their leaders using find. If the leaders are different, set the parent of leader of a to the leader of b.

DSA C

void union_sets(int a, int b) {
    // Your code here
}

Hint

Find leaders of both elements. If different, connect one leader to the other.

4

Perform unions and print the parent array

Call union_sets(0, 1), union_sets(1, 2), and union_sets(3, 4). Then print the parent array elements separated by spaces on one line.

DSA C

// Perform unions and print parent array below
// Your code here

Hint

Call the union functions as instructed. Then print each element of parent with a space.