🔗 Disjoint Set Union (DSU) – Comprehensive Study Guide

**Disjoint Set Union (DSU)** or **Union-Find** is a **data structure** that helps efficiently manage **disjoint sets** and is widely used in **graph theory** and **network connectivity** problems.

⚡ Why Use DSU?

  • ✅ **Efficiently checks if two elements belong to the same set.**
  • 📡 **Used in Graph Algorithms (Kruskal’s MST, Connected Components).**
  • 🚀 **Used in Dynamic Connectivity Problems.**
  • 🔍 **Can optimize operations using Path Compression & Union by Rank.**

📌 Basic Operations in DSU

📥 **1. Find Operation**

Finds the **representative (leader)** of a set to determine if two elements belong to the same set.

📤 **2. Union Operation**

Merges two disjoint sets into a single set.

📌 **Naïve Implementation (O(n) per operation)**


                int parent[1000];
            
                void makeSet(int n) {
                    for (int i = 0; i < n; i++) parent[i] = i;
                }
            
                int find(int v) {
                    if (parent[v] == v) return v; // Leader of the set
                    return find(parent[v]); // Recursive call
                }
            
                void unionSets(int a, int b) {
                    int rootA = find(a);
                    int rootB = find(b);
                    if (rootA != rootB) parent[rootA] = rootB;
                }

❌ **Why is This Inefficient?**

Because **Find takes O(n) time** in the worst case.

⚡ Optimized DSU: Union by Rank & Path Compression

📌 **1. Path Compression**

Reduces the height of the tree by pointing nodes directly to the root.


                int find(int v) {
                    if (parent[v] != v) parent[v] = find(parent[v]); // Path compression
                    return parent[v];
                }

📌 **2. Union by Rank**

Always attach the **smaller tree** under the **larger tree**.


                int parent[1000], rank[1000];
            
                void makeSet(int n) {
                    for (int i = 0; i < n; i++) {
                        parent[i] = i;
                        rank[i] = 0;
                    }
                }
            
                void unionSets(int a, int b) {
                    int rootA = find(a);
                    int rootB = find(b);
                    if (rootA != rootB) {
                        if (rank[rootA] > rank[rootB])
                            parent[rootB] = rootA;
                        else if (rank[rootA] < rank[rootB])
                            parent[rootA] = rootB;
                        else {
                            parent[rootB] = rootA;
                            rank[rootA]++;
                        }
                    }
                }

✅ **Why is This Efficient?**

  • 📌 **Find operation runs in O(α(n)) (Inverse Ackermann)**.
  • ⚡ **Almost constant time for real-world applications.**

🛠️ DSU in Graph Algorithms

📌 **1. Checking if a Graph is Connected**

We can use DSU to check if **all nodes belong to the same set**.

📌 **2. Kruskal’s Algorithm for Minimum Spanning Tree (MST)**

Kruskal’s Algorithm sorts edges and uses DSU to build an MST.


                struct Edge {
                    int u, v, weight;
                };
            
                bool cmp(Edge a, Edge b) {
                    return a.weight < b.weight;
                }
            
                int kruskal(vector &edges, int V) {
                    sort(edges.begin(), edges.end(), cmp);
                    makeSet(V);
                    int cost = 0;
                    for (Edge e : edges) {
                        if (find(e.u) != find(e.v)) {
                            unionSets(e.u, e.v);
                            cost += e.weight;
                        }
                    }
                    return cost;
                }

⏳ Time Complexity Analysis

Operation Naïve DSU Optimized DSU
Find O(n) O(α(n))
Union O(n) O(α(n))
Kruskal’s Algorithm O(E log V) O(E log V)

🌍 Real-World Applications of DSU

  • 📡 **Network Connectivity** – Checking if networks remain connected.
  • 🔗 **Social Network Friend Circles** – Detecting communities.
  • 🌉 **Kruskal’s Algorithm (Minimum Spanning Tree)**.
  • 🖥️ **Connected Components in Image Processing**.

🔗 Next Topics