templates · Graph traversal

Union-Find (DSU)

  • Edges or "same group" facts arrive one by one and you ask "are these two connected?"
  • "Which edge creates a cycle?" or "how many groups are left?"
  • Merging accounts, friend circles or network pieces, without walking the whole graph again

Union-Find (DSU)

the one rule

The invariant

Two items are in the same set exactly when find gives the same root for both.

write it from memory

The template

javajava.util.*
/** Disjoint sets over 0..n-1 with path compression and union by rank. */class DSU {    private final int[] parent;    private final int[] rank;    private int components;     DSU(int n) {        parent = new int[n];        rank = new int[n];        for (int i = 0; i < n; i++) parent[i] = i;    // everyone starts alone        components = n;    }     int find(int x) {        if (parent[x] != x) parent[x] = find(parent[x]); // point straight at the root        return parent[x];    }     /** Joins the sets of a and b; false if they were already together. */    boolean union(int a, int b) {        int ra = find(a), rb = find(b);        if (ra == rb) return false;                   // same set: this edge closes a cycle        if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }        parent[rb] = ra;                              // shorter tree hangs under the taller one        if (rank[ra] == rank[rb]) rank[ra]++;        components--;                                 // two sets became one        return true;    }     int components() {        return components;    }}

union returns false when both are already in one set. That one boolean answers most cycle questions.

fill in the blanks — only these lines change per problem

  1. line 10What the items are. Nodes 0..n-1 here; for 1-based input use n + 1, and for strings map each one to an index first.
  2. line 22What an already-joined pair means: the redundant edge, a broken "!=" rule, or a spare cable.
  3. line 26Extra data to update when two sets join: the count here, or a set size / sum kept at the root.

complexity

What it costs

time O(α(n)) per operation, amortized
Path compression plus union by rank keep trees almost flat. α(n) is the inverse Ackermann function, at most 4 for any real n.
space O(n)
Two int arrays of size n: parent and rank.

watch out

Common bugs

  • Writing parent[a] = b instead of linking the two roots. Then sets get split instead of merged.
  • Comparing parent[a] == parent[b] instead of find(a) == find(b). A parent is not always the root.
  • Forgetting 1-based node labels and making the array one too small.

use it

Practise it on

learn it properly