Union-Find (Disjoint Set Union)

Track connected components with path compression and union by size.

Est. 60 min Updated Suggest a fix
💡 Note
Prerequisites: arrays, trees, and the Graphs lesson. Disjoint Set Union (DSU), also called Union-Find, is designed for adding connections and answering connectivity queries; it is not a general graph traversal or shortest-path replacement.

Objectives: represent a partition efficiently

DSU maintains a partition of elements into disjoint sets. find(x) returns the representative (root) of x’s set; union(a, b) merges the two sets if they differ. This is useful when edges are added over time and we need to know whether two vertices are connected or whether an edge joins components. The structure is especially useful in Kruskal’s minimum spanning tree algorithm.

🎯 Pro Tip
This lesson teaches the data structure used by Kruskal’s algorithm. The Interview Problem-Solving Patterns → lesson has a separate DSU pattern summary and practice prompts, so we link there rather than duplicating that unit.

1. Parent forests and representatives

Initially, each element is its own parent and therefore forms a one-element set. A root points to itself. To find the representative of an element, follow parent pointers until reaching a root. A union connects one root beneath another. If we always attach arbitrarily, a chain can grow to length n, making find slow; balancing rules keep the forest shallow.

Initialize and find with path compression · C
void dsu_init(int parent[], int size[], int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        size[i] = 1;
    }
}

int dsu_find(int parent[], int x) {
    if (parent[x] != x)
        parent[x] = dsu_find(parent, parent[x]);
    return parent[x];
}

Path compression rewires visited nodes directly to the root during find. A later lookup along the same path then takes less work. This changes the forest shape but not which elements belong to each set. The recursive implementation is concise; iterative path halving is an alternative when avoiding recursion is important.

2. Union by size

After finding both roots, attach the smaller tree under the larger one. Update the size only at the new root. If both inputs already share a root, no merge occurs. The returned Boolean is useful to count successful merges or detect whether an undirected edge joined vertices already in the same component.

Union by size; true means two sets were merged · C
#include <stdbool.h>

bool dsu_union(int parent[], int size[], int a, int b) {
    int root_a = dsu_find(parent, a);
    int root_b = dsu_find(parent, b);
    if (root_a == root_b) return false;
    if (size[root_a] < size[root_b]) {
        int temp = root_a;
        root_a = root_b;
        root_b = temp;
    }
    parent[root_b] = root_a;
    size[root_a] += size[root_b];
    return true;
}

Union by rank is a related alternative. Rank estimates tree height before path compression; size records the number of members. Either balancing strategy combined with path compression gives near-constant amortized operations, conventionally written O(α(n)), where α is the inverse Ackermann function.

3. Connectivity and component counts

Two vertices are connected in the DSU’s current partition exactly when their representatives are equal. Keep a component count initialized to n and decrement it only when union succeeds. For a sequence of edge additions, this answers component counts without retraversing the entire graph after each change.

Process edges and maintain components · C
#include <stdbool.h>

int add_edges(int parent[], int size[], int components,
              const int edges[][2], int edge_count) {
    for (int i = 0; i < edge_count; i++) {
        if (dsu_union(parent, size, edges[i][0], edges[i][1]))
            components--;
    }
    return components;
}

bool dsu_connected(int parent[], int a, int b) {
    return dsu_find(parent, a) == dsu_find(parent, b);
}

For cycle detection in an undirected graph processed edge by edge, if an edge’s endpoints already have the same representative, adding that edge creates a cycle (assuming the input edge was not otherwise excluded by the problem). DSU cannot report the actual cycle path; DFS/BFS parent tracking is more suitable when the path itself is needed.

4. Worked trace: merge only when roots differ

Use five elements, numbered 0 through 4. Start with five components. After union(0, 1), there are four; after union(1, 2), there are three. The second call finds 1’s current root before merging, so it joins the entire existing component with 2 rather than treating 1 as an isolated set. Union(3, 4) creates a fourth connection but leaves two components. A repeated union(0, 2) is a no-op, so the count remains two.

The exact root chosen depends on the union order and size tie-breaking. A test should assert that 0, 1, and 2 have equal representatives, that 3 and 4 have equal representatives, that these groups differ, and that the component count is two. Avoid hard-coding a particular root value.

📌 Real World Example
For Kruskal, sorting edges is a separate step. DSU does not choose the cheapest edge; it only answers whether an edge would connect two different components. Keep the responsibilities separate: sorting determines candidate order, DSU prevents cycles.
Small connectivity demonstration (uses the helpers above) · C
#include <stdio.h>

int main(void) {
    int parent[5], size[5], components = 5;
    dsu_init(parent, size, 5);
    if (dsu_union(parent, size, 0, 1)) components--;
    if (dsu_union(parent, size, 1, 2)) components--;
    if (dsu_union(parent, size, 3, 4)) components--;
    if (dsu_union(parent, size, 0, 2)) components--;
    printf("connected(0, 2)=%d components=%d
",
           dsu_connected(parent, 0, 2), components);
    return 0;
}

The repeated merge does not lower the component count; the output reports 1 for connected and two components. These helpers assume every vertex id is in range, so validate external ids before indexing the parent and size arrays.

5. What DSU does not support

Operation or taskDSU fit?Reason
Add an undirected connection; query connectivityYesComponents only merge, so parent forest captures the partition
Remove arbitrary edgesUsually noA merge cannot be undone by ordinary DSU
Return a path or distanceNoIt stores component membership, not graph routes
Kruskal edge acceptanceYesReject an edge when endpoints already share a root
⚠️ Important
Ordinary DSU is optimized for monotone additions: connected components only merge. Supporting deletions requires more advanced offline or dynamic-connectivity techniques; do not pretend a removed edge can simply be “un-unioned.”

6. A second connectivity check

Start with {0}, {1}, {2}, {3}, {4}. Union(0, 1) and union(1, 2) create one component {0,1,2}. Union(3, 4) creates {3,4}; the component count is now two. A query for 0 and 2 returns connected; a query for 0 and 4 does not. Trying to union(0, 2) returns false because it is already one set and leaves the count unchanged.

Representatives are implementation details: after different valid union orders, the root for {0,1,2} may differ. Tests should verify connectivity and component counts, not assume a particular root number.

7. Common mistakes

  • Unioning raw vertices instead of their roots: attach representatives after calling find, otherwise the sets may not combine correctly.
  • Updating the child root’s size: size is meaningful at roots. Add into the surviving root only.
  • Decrementing components on every edge: duplicate or cycle-forming edges may not merge two sets. Decrement only when union reports success.
  • Expecting DSU to handle deletions or return routes: those operations need different data structures or algorithms.

8. Practice

  1. Implement a component counter for n vertices and a list of undirected edges. Compare it with DFS on the same small input.
  2. Return the number of successful merges, then use it to identify whether an edge closes a cycle.
  3. Extend DSU with a component-size query. Explain why the answer is valid only when reading the root’s size.
  4. Process edges in two different orders and show that the representative may change while connectivity stays the same.
  5. Design test cases for n = 1, repeated edges, self-loops, and disconnected vertices; state any required input validation.

🎯 Key Takeaways

  • ✓DSU represents a partition as a forest of parent pointers.
  • ✓Find returns a component representative; union merges distinct roots.
  • ✓Path compression and union by size keep operations near constant amortized time.
  • ✓Decrement the component count only when a union actually merges two sets.
  • ✓Ordinary DSU supports additions, not arbitrary edge deletions or path queries.
  • ✓Kruskal uses DSU to decide whether an edge joins two different components.

Next

Use DSU to build a minimum spanning tree with Kruskal, then compare it with Prim’s approach.

Lesson 19 · Minimum Spanning Trees — Kruskal and Prim →

HELP US IMPROVE

How was this lesson?

Your note is shared with the Chaduvuko team for review. Please don’t include personal or sensitive information.

Choose your feedback

Spotted a mistake or something unclear? Suggest a fix on GitHub or email us. Select the text first and it is quoted for you.

Share

Discussion

0

Have a better approach? Found something outdated? Share it — your knowledge helps everyone learning here.

Continue with GitHub
Loading...