Union-Find (DSU) | Graph Patterns

🔗

Union-Find (Disjoint Set Union)

Path compression + union by rank — near-O(1) per operation for connectivity queries

ConnectivityDSU Path CompressionUnion by Rank

Time: O(α(n)) ≈ O(1) per op Space: O(n)

When to Use

Check if two nodes are in the same connected component
Count number of connected components dynamically
Detect cycle in an undirected graph
Kruskal's MST — union edges by cheapest first
Grid problems — merge cells/islands dynamically

Complexity

find(x)	O(α(n)) amortized
union(x, y)	O(α(n)) amortized
Space	O(n) — parent[] + rank[]
α(n)	Inverse Ackermann — practically ≤ 4

Problem Given n = 6 cities and a list of connections, find the number of provinces (groups of directly or indirectly connected cities). Apply Union-Find: merge connected cities with union by rank, then count remaining root nodes to get the province count.
Input: n = 6, connections = [[0,1],[2,3],[1,2],[4,5]] · Answer: 2 provinces — {0,1,2,3} and {4,5}

INIT

parent[]

rank[]

Step 0 / 8

Init Union Find Path Compress Query

Initialize: each node is its own parent (its own component).

parent[i] = i; rank[i] = 0; // for all i

Java Pattern Template skeleton only

// Union-Find (Disjoint Set Union) — pattern skeleton
int[] parent, rank;

void init(int n) {
    parent = new int[n];
    rank   = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i; // each node is its own root
}

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

boolean union(int x, int y) {
    int px = find(x), py = find(y);
    if (px == py) return false; // already same component
    if (rank[px] < rank[py]) { int t = px; px = py; py = t; } // swap so px has higher rank
    parent[py] = px; // merge smaller tree under larger
    if (rank[px] == rank[py]) rank[px]++;
    return true;
}

boolean connected(int x, int y) { return find(x) == find(y); }

🎯 Practice Problems

#1971 Find if Path Exists E #547 Number of Provinces M #323 Connected Components M #684 Redundant Connection M #721 Accounts Merge M #947 Most Stones Removed M