Chapter 71

Home

Refactoring: Union-Find

Running DFS every time edges are added is O(V+E) per query. Union-Find (DSU) tracks connected components dynamically — find and union in nearly O(1) time with path compression.

Before: DFS for Connectivity

C++ — O(V+E) per connectivity query

// Each time we add an edge or ask "are u and v connected?"
// we run a DFS. For Q queries: O(Q × (V+E)).

After: Union-Find (DSU)

C++ — Union-Find with path compression

struct DSU {
    vector parent, sz;
    DSU(int n) : parent(n), sz(n, 1) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }

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

    void unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        parent[b] = a;
        sz[a] += sz[b];
    }

    bool same(int a, int b) { return find(a) == find(b); }
};

// Near O(1) per operation (inverse Ackermann)

Rust — DSU

struct DSU {
    parent: Vec,
    size: Vec,
}
impl DSU {
    fn new(n: usize) -> Self {
        DSU { parent: (0..n).collect(), size: vec![1; n] }
    }
    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            self.parent[x] = self.find(self.parent[x]);
        }
        self.parent[x]
    }
    fn unite(&mut self, a: usize, b: usize) {
        let (a, b) = (self.find(a), self.find(b));
        if a == b { return; }
        if self.size[a] < self.size[b] { swap(a, b); }
        self.parent[b] = a;
        self.size[a] += self.size[b];
    }
}

Key Takeaways