Step 7 of 7

Union-find (disjoint sets)

Some questions come up while edges are still arriving one at a time: "after these cables were plugged in, are servers 3 and 8 connected?", "does this new road create a loop?", "how many separate friend groups are there now?". Running a fresh BFS after every edge would be O(V + E) each time. Union-find (also called disjoint set union) answers them in nearly O(1) per operation.

Every element points to a parent in its group; the element that points to itself is the group's root, its representative. Two operations:

• find(x): follow parents up to the root. Two elements are in the same group exactly when they have the same root.
• union(a, b): find both roots; if they differ, make one root point to the other. The groups merge.

struct Groups {
    parent: Vec<usize>,
}

impl Groups {
    fn new(n: usize) -> Self {
        Groups { parent: (0..n).collect() } // everyone starts alone
    }

    fn find(&self, mut x: usize) -> usize {
        while self.parent[x] != x {
            x = self.parent[x];
        }
        x
    }

    fn union(&mut self, a: usize, b: usize) -> bool {
        let (ra, rb) = (self.find(a), self.find(b));
        if ra == rb {
            return false; // already in the same group
        }
        self.parent[ra] = rb;
        true
    }
}

fn main() {
    // ana = 0, ben = 1, cy = 2, dee = 3, eve = 4
    let mut g = Groups::new(5);
    g.union(0, 1); // ana and ben become friends
    g.union(3, 4);
    g.union(1, 2);
    println!("ana and cy: {}", g.find(0) == g.find(2));
    println!("ana and eve: {}", g.find(0) == g.find(4));
    println!("ben-cy again merged something: {}", g.union(1, 2));
}

ana and cy: true
ana and eve: false
ben-cy again merged something: false

Two tricks that make it fast

This simple version can build long chains of parents (each union hangs one root under another), and then find is O(n). Two small changes fix that:

• Union by size: keep a size for each root and always hang the smaller group under the bigger one. Trees then stay at most log₂ n deep.
• Path compression: after find(x) has found the root, go up the path a second time and point every node on it directly at the root. The next find on any of them is one step. Because it changes parent, find now takes &mut self.

With both, a sequence of operations costs O(α(n)) each on average, where α is the inverse Ackermann function: at most 4 for any input that fits in the universe. In practice, constant.

Union-find shows up in Kruskal's algorithm for minimum spanning trees (connect everything as cheaply as possible), detecting a cycle as edges arrive, merging duplicate customer accounts that share an email or phone number, and grouping pixels in image processing.

Common mistakes

• Linking the elements instead of their roots. parent[a] = b only moves a, and breaks the group a was in. Always link find(a) and find(b).
• Forgetting to check ra == rb. Linking a root to itself is harmless, but then your "groups" counter and your "this edge made a cycle" logic are wrong.
• Keeping sizes for non-roots. Only a root's size entry is meaningful; update the new root's size when merging.

Your task

Write a UnionFind with union by size and path compression:

• fn new(n: usize) -> Self: elements 0..n, each alone
• fn find(&mut self, x: usize) -> usize: the root, compressing the path
• fn union(&mut self, a: usize, b: usize) -> bool: merge; false if they were already together
• fn group_count(&self) -> usize: how many separate groups there are
• fn group_size(&mut self, x: usize) -> usize: the size of x's group

The tests merge 200,000 elements in a pattern that builds a 200,000-long chain without the two tricks.

Challenge 2

A network engineer plugs in cables one by one between n offices (0..n). The design was supposed to be a tree (no loops), but someone added an extra cable. Write fn first_redundant(n: usize, cables: &[(usize, usize)]) -> Option<(usize, usize)> that returns the first cable (in the given order) that connects two offices that were already connected through earlier cables, or None if no cable is redundant.

Write a small union-find inside (a parent Vec and a find function are enough here, though union by size and path compression don't hurt): for each cable, if both ends already have the same root, that's the one.

Challenge 3

Kruskal's algorithm. The company has n offices and a list of possible cable routes (a, b, cost). Find the cheapest set of cables that connects all offices (a minimum spanning tree). Write fn min_cable_cost(n: usize, options: &[(usize, usize, u64)]) -> Option<u64>: the total cost, or None if the offices can't all be connected. With one office (or none), the cost is 0.

Kruskal is short with union-find: sort the options by cost, cheapest first, and take each cable whose ends are not yet connected (union returns true), skipping the rest. You're done when n - 1 cables are taken. The tests include 100,000 offices and 200,000 options.

Previous: Binary trees with Option<Box<Node>>