Chapter 10: Union-Find (Disjoint Set Union)

10.1 Core Concept: Finding the Boss

Imagine a martial arts world. There are N warriors, each with their own sect and own master. Union-Find handles two operations:

1. Union: If warrior A fights warrior B and loses, A swears loyalty to B. A’s sect joins B’s.
2. Find: To check if warrior X and warrior Y belong to the same clan, ask who their final boss is. If the bosses are the same person, they belong to the same group.

10.2 Data Structure

We maintain an array fa[N] (father):

• fa[i] = k means i’s direct superior is k.
• If fa[i] == i, then i is the clan leader (root).

10.2.1 Initialization

At the start, everyone is their own boss.

int fa[1005];
 
void init(int n) {
    for (int i = 1; i <= n; i++)
        fa[i] = i;
}

10.2.2 Find with Path Compression

This is the soul of union-find. Without optimization, finding the boss might climb the tree step by step, resulting in O(N) per query.

Path compression: When node x first finds its root, we set every visited node’s parent directly to the root. Next time, finding the boss is one step.

int find(int x) {
    if (fa[x] == x)
        return x;
    return fa[x] = find(fa[x]);
}

10.2.3 Union

To merge the clans of x and y, link their roots.

void merge(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        fa[rootX] = rootY;
    }
}

10.3 Complexity

Thanks to path compression (and optionally union by rank), the structure flattens over time. The operations run in O(α(N)), where α(N) is the inverse Ackermann function. It grows so slowly that even for the number of atoms in the universe, α(N) ≤ 4. So in practice, each union/find is effectively O(1).

10.4 Advanced Applications

10.4.1 Connected Components

Problem: Given a graph with N nodes and M edges, how many independent connected components are there?

Solution: For each edge (u, v), call merge(u, v). At the end, count how many fa[i] == i remain—they are the roots.

10.4.2 Enemy-Based Union-Find (Bi-coloring)

Scenario: P1525 [NOIP2010 Advanced] Jailing Criminals. If A and B are enemies and B and C are enemies, then A and C should be allies.

Trick: Use an array of size 2*N.

• 1..N represent the individuals.
• N+1..2N represent “their enemies”.

If A and B are enemies, merge(A, B + N) and merge(B, A + N).

10.4.3 Minimum Spanning Tree (Kruskal)

We’ll cover this in the graph section, but the idea is: Sort edges by weight. For each edge, if the endpoints are not already in the same set (checked via find), add the edge and merge their sets.

🧠 Summary & Practice

Union-Find is the go-to structure for merging disjoint sets. Its code is short, easy to implement, and a staple for contest scoring.

Practice problems:

1. P1551 Relatives (Luogu): a basic template.
2. P3367 Union-Find Template: test your implementation with N = 10^4.
3. LeetCode 547 Number of Provinces: count connected components.

So far we’ve tackled arrays, stacks, queues, and sets—linear data structures. Next chapter we enter graph theory, a world of nodes and edges.