Union Find with Path Compression 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 < 6; i++) p[i] = i;
    unite(1, 2); unite(2, 3); unite(4, 5);
    printf("Find(3): %d\n", find(3));
    printf("Find(5): %d\n", find(5));
    printf("Find(2): %d\n", find(2));
}

C Output

Input:
Union(1,2), Union(2,3), Union(4,5)
Output:
Find(3): 3
Find(5): 5
Find(2): 3

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(6); for (int i = 0; i < 6; i++) p[i] = i;
    unite(p, 0, 1); unite(p, 1, 2); unite(p, 3, 4);
    cout << "Find(2): " << find(p, 2) << endl;
    cout << "Find(4): " << find(p, 4) << endl;
    cout << "Find(0): " << find(p, 0) << endl;
}

C++ Output

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

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[6]; for (int i = 0; i < 6; i++) p[i] = i;
        unite(p, 2, 4); unite(p, 4, 5); unite(p, 0, 3);
        System.out.println("Find(5): " + find(p, 5));
        System.out.println("Find(3): " + find(p, 3));
        System.out.println("Find(2): " + find(p, 2));
    }
}

JAVA Output

Input:
Union(2,4), Union(4,5), Union(0,3)
Output:
Find(5): 5
Find(3): 3
Find(2): 5

Python Program

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

Python Output

Input:
Union(0,2), Union(2,5), Union(1,3)
Output:
Find(5): 5
Find(3): 3
Find(0): 5

In-Depth Explanation

Example

Let us consider the Python example. We do:

Union(0,2) → parent[2] = 0  

Union(2,5) → parent[5] = find(2) = 0 → parent[5] = 0  

Now, 0, 2, and 5 are in the same set and 0 is the representative.

Following compression, find(5) sets parent[5] = 0, and the tree gets flattened.

Real-Life Analogy

Suppose you have a large corporation with several departments. Each employee has a manager, and the manager can have another manager.

To get the topmost manager of an employee, you trace upwards (similar to find(x)).

With path compression, after finding the CEO, you mark all the employees in between directly pointing to the CEO — so future lookups are instantaneous.

Why It Matters

Path compression significantly enhances performance from linear to almost constant time per operation.

DSU is applied in:

Cycle detection

Network connectivity

Minimum Spanning Trees (Kruskal's Algorithm)

Cluster analysis and group tracking

This optimization is particularly crucial when you are dealing with millions of union-find operations in big datasets.

Learning Insights

You learn with this program:

How recursion transforms trees into a flat structure

How find() can optimize itself over time

The elegance of using greedy strategy + recursion

A popular building block of graph algorithms

This is one of the quickest subroutines in the entire competitive programming arena.

Interview & Real-World Application

Path compression is applied in:

Kruskal's MST implementations

Connected components

Union-by-rank + path compression designs

Network partitioning problems

Real-world systems apply this in:

Social networks for group identification

Distributed systems for resource coordination

Cluster management in cloud services and databases

Union Find with Path Compression is a basic data structure that combines recursion, optimization, and set tracking efficiently into a single beautiful solution. It's the core of Kruskal's algorithm and appears anywhere from social network group discovery to network stability analysis. Path compression makes sure that each find operation takes less and less time, bringing down the tree depth and enabling nearly constant-time queries. With briefest examples in C, C++, Java, and Python, this tutorial teaches you not only the code, but the logic, intent, and strength behind it — to help you prepare for interviews, contests, and production systems.