Disjoint Set Union (DSU) in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>
int p[10];
int find(int x) { return p[x] == x ? x : (p[x] = find(p[x])); }
void unite(int a, int b) { p[find(a)] = find(b); }
int main() {
    for (int i = 0; i < 5; i++) p[i] = i;
    unite(0, 2); unite(4, 2); unite(3, 1);
    printf("Find(4): %d\n", find(4));
    printf("Find(3): %d\n", find(3));
}

C Output

Input:
Union(0,2), Union(4,2), Union(3,1)
Output:
Input: DSU operations

Output:
Find(4): 2
Find(3): 1

C++ Program

#include <iostream>
#include <vector>
using namespace std;
int find(vector<int>& p, int x) {
    return p[x] == x ? x : p[x] = find(p, p[x]);
}
void unite(vector<int>& p, int a, int b) {
    p[find(p, a)] = find(p, b);
}
int main() {
    vector<int> p(5); for (int i = 0; i < 5; i++) p[i] = i;
    unite(p, 1, 4); unite(p, 2, 3); unite(p, 4, 3);
    cout << "Find(1): " << find(p, 1) << "\n";
    cout << "Find(2): " << find(p, 2) << "\n";
}

C++ Output

Input:
Union(1,4), Union(2,3), Union(4,3)
Output:
Input: DSU state

Output:
Find(1): 3
Find(2): 3

JAVA Program

import java.util.*;
class Main {
    static int find(int[] p, int x) {
        return p[x] == x ? x : (p[x] = find(p, p[x]));
    }
    static void unite(int[] p, int a, int b) {
        p[find(p, a)] = find(p, b);
    }
    public static void main(String[] args) {
        int[] p = new int[5]; for (int i = 0; i < 5; i++) p[i] = i;
        unite(p, 0, 1); unite(p, 1, 2); unite(p, 3, 4);
        System.out.println("Find(2): " + find(p, 2));
        System.out.println("Find(4): " + find(p, 4));
    }
}

JAVA Output

Input:
Union(0,1), Union(1,2), Union(3,4)
Output:
Input: Disjoint set unions

Output:
Find(2): 1
Find(4): 4

Python Program

p = list(range(6))
def find(x): return x if p[x] == x else find(p[x])
def union(x, y): p[find(x)] = find(y)
union(1, 2); union(2, 5); union(0, 3)
print("Find(1):", find(1))
print("Find(5):", find(5))
print("Find(3):", find(3))

Python Output

Input:
Union(1,2), Union(2,5), Union(0,3)
Output:
Input: Operations on DSU

Output:
Find(1): 5
Find(5): 5
Find(3): 3

In-Depth Explanation

Example

In the example in Python:

Union(1, 2)

Union(2, 5)

All three members — 1, 2, and 5 — now share the same set. Therefore, calling Find(1) will give the representative or root, which is 5 here.

Real-Life Analogy

Suppose a group of students was setting up teams.

Each individual was alone initially. When two individuals shook hands (union), they were now on the same team.

When you query "What team is Student X on?" (find), you receive their team leader.

Eventually, you can determine if two students belong to the same group or not — without enumerating the entire team.

Why It Matters

DSU is among the most significant data structures of graph algorithms. It drives:

Cycle detection in Kruskal's MST

Connected components detection

Grouping problems such as network partitioning or user clustering

With path compression, find() is almost constant-time.

Learning Insights

This instructs:

Effective set merging

Recursion and reference tracking

Greedy MST algorithm behavior such as that of Kruskal

Optimization using path compression and union by rank

It teaches effective algorithmic concepts via elementary operations. 

Interview & Real-World Application

DSU appears in:

Competitive programming

System design problems

Graph cycle detection

Cluster detection in social networks or data sets

Applied to:

Kruskal's MST

Social network clustering

Dynamic connectivity problems

Real-time group merging in online games or systems

Disjoint Set Union (DSU) or Union-Find is one of the most powerful utilities for dynamically dealing with merging groups and connectivity queries. It is the foundation for Kruskal's Algorithm, aids in cycle detection, and is crucial in dealing with connected components of a graph. By learning DSU, you equip yourself not only with a large variety of algorithmic problems but also with a solid grasp of how grouping logic functions in actual systems such as clustering users or handling network partitions. The C, C++, Java, and Python code examples provide you with a practical means of internalizing the logic, and the thorough explanation provides conceptual clarity for interviews and everyday applications.