Union-find

Deep dive

How it works

In: n elements numbered 0..n-1, then a stream of union(a, b) and find(x) calls · Out: same-set answers, set sizes, the component count · State: parent and size arrays that persist across calls, 8 B per element · Cost: O(α(n)) amortized per operation, α(n) ≤ 4 in practice

1. Init: parent[i] = i, size[i] = 1.
2. find(x): while parent[x] ≠ x, set parent[x] = parent[parent[x]] (halving), then x = parent[x].
3. union(a, b): ra = find(a), rb = find(b). If they are equal, return false. Otherwise attach the smaller-size root under the larger and add the sizes.
4. Components: count successful unions, components = n − unions. size[find(x)] is the size of x's set.

before find(4):  4 → 3 → 2 → 1 → 0 (root)
after halving:   4 → 2 → 0,  3 → 2,  1 → 0   every other node on the path skips one level

Code

pub struct Dsu { parent: Vec<u32>, size: Vec<u32> }

impl Dsu {
    pub fn new(n: usize) -> Self { Dsu { parent: (0..n as u32).collect(), size: vec![1; n] } }

    pub fn find(&mut self, mut x: u32) -> u32 {
        while self.parent[x as usize] != x {
            let gp = self.parent[self.parent[x as usize] as usize];
            self.parent[x as usize] = gp; // path halving: skip one level
            x = gp;
        }
        x
    }

    /// Returns false if a and b were already in the same set.
    pub fn union(&mut self, a: u32, b: u32) -> bool {
        let (mut ra, mut rb) = (self.find(a), self.find(b));
        if ra == rb { return false; }
        if self.size[ra as usize] < self.size[rb as usize] { std::mem::swap(&mut ra, &mut rb); }
        self.parent[rb as usize] = ra; // smaller tree under larger: depth <= log2 n
        self.size[ra as usize] += self.size[rb as usize];
        true
    }

    pub fn set_size(&mut self, x: u32) -> u32 { let r = self.find(x); self.size[r as usize] }
}

use std::sync::atomic::{AtomicU32, Ordering::Relaxed};

/// Lock-free variant. Invariant: parent[x] >= x (link the smaller index under the larger),
/// so no cycles can form. Every value read is a valid ancestor, so Relaxed suffices.
/// Randomly permute element IDs first to keep trees shallow in expectation.
pub struct ConcurrentDsu { parent: Vec<AtomicU32> }

impl ConcurrentDsu {
    pub fn new(n: usize) -> Self { ConcurrentDsu { parent: (0..n as u32).map(AtomicU32::new).collect() } }

    pub fn find(&self, mut x: u32) -> u32 {
        loop {
            let p = self.parent[x as usize].load(Relaxed);
            if p == x { return x; }
            let gp = self.parent[p as usize].load(Relaxed);
            let _ = self.parent[x as usize].compare_exchange_weak(p, gp, Relaxed, Relaxed); // best-effort halving
            x = gp;
        }
    }

    pub fn union(&self, a: u32, b: u32) -> bool {
        loop {
            let (ra, rb) = (self.find(a), self.find(b));
            if ra == rb { return false; }
            let (lo, hi) = if ra < rb { (ra, rb) } else { (rb, ra) };
            // succeeds only if `lo` is still a root; otherwise someone linked it, so retry
            if self.parent[lo as usize].compare_exchange(lo, hi, Relaxed, Relaxed).is_ok() { return true; }
        }
    }
}

Complexity and constants

• Amortized O(α(n)) per operation (Tarjan 1975). Union by size alone gives O(log n) worst case. Compression alone gives O(log n) amortized.
• In practice, find touches 1-3 parent entries. The cost is cache misses on random elements: order of 10-50 ns per operation once n × 4 B exceeds the LLC, a few ns when it fits.
• Connected components of an edge list with E unions: O(E α(V)) with streaming access to the edges. The edges never need to be stored as adjacency lists.

Efficiency

• Cost: measured with the code above (sequential Dsu) on an Apple M4 Pro, one thread, n random unions on n elements, best of 3: 2^20 elements take 10.2 ms (9.7 ns per union, two finds), 2^24 elements 715 ms (43 ns per union); a find on the finished structure costs 1.3 ns and 6.3 ns. Memory 8 B per element. Bound: cache misses on random elements.
• Levers:
  • path halving on top of union by size — 1.41× at 2^20 (9.7 vs 13.7 ns per union), none at 2^24 (43 vs 40 ns) (measured) — small and mid-size n
  • one array, negative value = root with −size — one cache miss fewer per root lookup (Implementation notes) — n beyond the cache
  • dense u32 ids instead of a hash map — about an order of magnitude (Implementation notes) — string or 64-bit keys
  • sampling-based parallel components — fastest parallel connected components on large graphs (Sutton et al. 2018; Implementation notes) — billions of edges
• Naive → standard → state of the art:
  • quick-find (a component label per element) · O(n) per union
  • union by size, no compression (measured variant) · 13.7 ns per union at 2^20
  • union by size plus path halving (code above) · 9.7 ns at 2^20, 43 ns at 2^24; lock-free or sampling variants for many threads

Implementation notes

• Store size only at roots (or merge parent and size into one array: negative values = root with −size). One array means one cache miss less.
• Sparse IDs (strings, 64-bit hashes): compress them to dense u32 indices first. A HashMap-based DSU is about an order of magnitude slower.
• Weighted / potential DSU: store each node's offset relative to its parent (parity, difference). This answers "is x − y = k consistent?" for bipartiteness checks and difference constraints. Update the offsets during compression.
• Rollback DSU: union by size without compression plus an undo stack. This supports offline dynamic connectivity (divide and conquer over time).
• Parallel components: Afforest / Shiloach-Vishkin-style hooking with sampling. These are the fastest parallel connected components on large graphs.

Pitfalls

• Recursive find with full compression on a degenerate chain (no union by size) overflows the stack. Use the iterative halving loop.
• Linking non-roots (parent[a] = b instead of parent[find(a)] = find(b)), or reading size[x] for a non-root x.
• Forgetting that find mutates: it can't be called through &self in the sequential version (use Cell or the atomic version if needed).
• Concurrent union by rank or size races: two threads can link roots in a cycle. Use an ID or priority order as above.
• Expecting set enumeration: union-find doesn't list members. Keep a linked "next" ring per set if you need it.

Variants and alternatives

In production

Graph algorithms: Kruskal implementations (minimum spanning tree), the GAP benchmark's connected components (Afforest, Sutton et al. 2018). Compilers: rustc type inference (the ena crate's unification tables), LLVM EquivalenceClasses, Steensgaard-style alias analysis (Steensgaard 1996). Image processing: OpenCV connectedComponents (union-find-based labeling; Wu, Otoo, Suzuki 2009). Physics: percolation simulations (Newman, Ziff 2000).

Implementations

Sources

• B. Galler, M. Fischer, An Improved Equivalence Algorithm, CACM, 1964. paper
• R. Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, JACM, 1975. paper
• R. Tarjan, J. van Leeuwen, Worst-Case Analysis of Set Union Algorithms, JACM, 1984. paper
• R. Anderson, H. Woll, Wait-free Parallel Algorithms for the Union-Find Problem, STOC, 1991. paper
• S. Jayanti, R. Tarjan, A Randomized Concurrent Algorithm for Disjoint Set Union, PODC, 2016. paper
• M. Sutton, T. Ben-Nun, A. Barak, Optimizing Parallel Graph Connectivity Computation via Subgraph Sampling, IPDPS, 2018. paper · code
• M. Newman, R. Ziff, Efficient Monte Carlo Algorithm and High-Precision Results for Percolation, Physical Review Letters 85(19), 2000. paper
• K. Wu, E. Otoo, K. Suzuki, Optimizing two-pass connected-component labeling algorithms, Pattern Analysis and Applications 12(2), 2009. paper