Union Find Disjoint Set Kruskal's MST & Connected Components

Introduction

Union-Find, also known as the Disjoint Set, is a powerful data structure used to efficiently manage a collection of non-overlapping sets. It supports two main operations:

• Find: Determine which set an element belongs to
• Union: Merge two sets into one

This structure plays a crucial role in solving graph problems like connected components and Kruskal’s Minimum Spanning Tree (MST).

For Pakistani students preparing for coding interviews, university exams, or competitive programming contests (like ICPC regionals or Codeforces), mastering Union-Find can give you a strong advantage. Whether you're studying in Lahore, Karachi, or Islamabad, this concept appears frequently in DSA courses and real-world applications.

Prerequisites

Before diving into Union-Find, make sure you understand:

• Basic programming (C++, Java, or Python)
• Arrays and indexing
• Recursion (helpful but not mandatory)
• Basic graph concepts (nodes, edges)
• Sorting algorithms (important for Kruskal’s algorithm)

Core Concepts & Explanation

Set Representation Using Trees

In Union-Find, each set is represented as a tree. Each node points to a parent, and the root node is the representative of the set.

Example:

Suppose Ahmad, Ali, and Fatima are in the same group:

Ahmad → Ali → Fatima (root)

Here:

• Fatima is the representative (root)
• Ahmad and Ali belong to Fatima’s set

We store this structure using an array:

parent[i] = parent of i

Path Compression Optimization

The Find operation can become slow if trees are deep. To fix this, we use Path Compression.

Whenever we call find(x), we make all nodes in the path directly point to the root.

Before:

Ahmad → Ali → Fatima

After find(Ahmad):

Ahmad → Fatima
Ali   → Fatima

This drastically improves performance.

Union by Rank (or Size)

When merging two sets, we attach the smaller tree under the larger one to keep the tree shallow.

• Rank = approximate height of tree
• Attach lower-rank tree under higher-rank tree

This ensures operations are nearly constant time: O(α(n)), where α is the inverse Ackermann function (extremely small).

Practical Code Examples

Example 1: Basic Union-Find Implementation

#include <iostream>
using namespace std;

const int N = 1000;
int parent[N];
int rankArr[N];

// Initialize sets
void makeSet(int n) {
    for(int i = 0; i < n; i++) {
        parent[i] = i;
        rankArr[i] = 0;
    }
}

// Find with path compression
int findSet(int x) {
    if(parent[x] != x)
        parent[x] = findSet(parent[x]);
    return parent[x];
}

// Union by rank
void unionSet(int a, int b) {
    int rootA = findSet(a);
    int rootB = findSet(b);

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

int main() {
    makeSet(5);

    unionSet(0, 1);
    unionSet(1, 2);

    cout << findSet(2) << endl;
}

Line-by-line Explanation:

• parent[N]: Stores parent of each node
• rankArr[N]: Stores rank (tree height approximation)
• makeSet: Initializes each node as its own parent
• findSet: Recursively finds root and compresses path
• unionSet: Merges two sets using rank optimization
• main: Demonstrates merging and finding sets

Example 2: Real-World Application — Kruskal’s MST

Let’s say we want to connect cities in Pakistan (Lahore, Karachi, Islamabad) with minimum road cost.

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v, weight;
};

bool compare(Edge a, Edge b) {
    return a.weight < b.weight;
}

int parent[100];

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

void unionSet(int a, int b) {
    parent[findSet(a)] = findSet(b);
}

int main() {
    int n = 4;
    vector<Edge> edges = {
        {0,1,10}, {1,2,15}, {0,2,5}, {2,3,20}
    };

    sort(edges.begin(), edges.end(), compare);

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

    int totalCost = 0;

    for(auto edge : edges) {
        if(findSet(edge.u) != findSet(edge.v)) {
            unionSet(edge.u, edge.v);
            totalCost += edge.weight;
            cout << "Edge added: " << edge.u << "-" << edge.v << endl;
        }
    }

    cout << "Minimum Cost: " << totalCost << endl;
}

Line-by-line Explanation:

• Edge struct: Stores source, destination, and weight
• compare: Sorts edges by weight
• edges vector: Represents graph connections
• sort: Required for Kruskal’s algorithm
• findSet: Checks if adding edge forms a cycle
• unionSet: Connects components
• Loop: Adds edges if no cycle is formed
• totalCost: Stores MST cost

Common Mistakes & How to Avoid Them

Mistake 1: Forgetting Path Compression

Without path compression, your solution may pass small tests but fail large ones.

❌ Wrong:

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

✅ Correct:

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

Mistake 2: Not Using Union by Rank

If you always attach one tree under another without considering size, trees become deep.

❌ Wrong:

parent[rootA] = rootB;

✅ Correct:

if(rankArr[rootA] < rankArr[rootB])
    parent[rootA] = rootB;

Mistake 3: Incorrect Initialization

Forgetting to initialize parent[i] = i causes wrong results.

Practice Exercises

Exercise 1: Count Connected Components

Problem:
Given n students in a university and friendships between them, find the number of friend groups.

Solution:

int countComponents(int n, vector<pair<int,int>> edges) {
    vector<int> parent(n);
    
    for(int i = 0; i < n; i++)
        parent[i] = i;

    function<int(int)> findSet = [&](int x) {
        if(parent[x] != x)
            parent[x] = findSet(parent[x]);
        return parent[x];
    };

    for(auto e : edges) {
        int a = findSet(e.first);
        int b = findSet(e.second);
        if(a != b)
            parent[a] = b;
    }

    set<int> uniqueSets;
    for(int i = 0; i < n; i++)
        uniqueSets.insert(findSet(i));

    return uniqueSets.size();
}

Explanation:

• Merge friends into sets
• Count unique roots

Exercise 2: Detect Cycle in Graph

Problem:
Check if an undirected graph contains a cycle.

Solution:

bool hasCycle(int n, vector<pair<int,int>> edges) {
    vector<int> parent(n);

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

    function<int(int)> findSet = [&](int x) {
        if(parent[x] != x)
            parent[x] = findSet(parent[x]);
        return parent[x];
    };

    for(auto e : edges) {
        int u = findSet(e.first);
        int v = findSet(e.second);

        if(u == v)
            return true;

        parent[u] = v;
    }

    return false;
}

Explanation:

• If two nodes already share the same root → cycle exists

Frequently Asked Questions

What is Union-Find used for?

Union-Find is used to efficiently manage groups of connected elements. It is commonly used in graph algorithms like Kruskal’s MST and for detecting connected components.

How do I optimize Union-Find?

Use path compression in the find operation and union by rank when merging sets. These optimizations make operations nearly constant time.

What is the time complexity of Union-Find?

With optimizations, each operation runs in O(α(n)), which is almost constant for practical input sizes.

How do I apply Union-Find in real life?

It can be used in network connectivity (e.g., internet providers in Pakistan), social networks (friend groups), and clustering problems.

Is Union-Find better than DFS/BFS?

For dynamic connectivity problems, Union-Find is faster and simpler than DFS/BFS. However, DFS/BFS is better for traversal and path-related problems.

Summary & Key Takeaways

• Union-Find (Disjoint Set) efficiently manages connected components
• Two main operations: Find and Union
• Path Compression and Union by Rank optimize performance
• Essential for Kruskal’s MST and cycle detection
• Runs in nearly constant time
• Widely used in competitive programming and real-world systems

Next Steps & Related Tutorials

To strengthen your DSA skills further, explore these tutorials on theiqra.edu.pk:

• Learn Graph Algorithms to understand BFS, DFS, and shortest paths
• Master Sorting Algorithms like QuickSort and MergeSort
• Study Greedy Algorithms for problems like Kruskal and Prim
• Practice Data Structures like Trees and Heaps for advanced problem solving

By combining Union-Find with these topics, you’ll be well-prepared for coding interviews, university exams, and platforms like LeetCode and Codeforces.

Keep practicing, and remember: every expert was once a beginner. 🚀