If you've ever had to solve a problem involving connected components—like checking if two servers in a massive data center are part of the same subnet or determining if a graph has a cycle—you've likely run into the Union-Find (or Disjoint Set Union) pattern. It's an elegant structure, but when you first implement it in Rust, it's easy to write code that is technically correct but practically useless for large datasets.

The trap of the linear chain

The most intuitive way to build a Union-Find is to use a simple array where each index represents an element and the value at that index is its parent. If an element is its own parent, it's the root of that set. In this naive version, the find operation just follows the parent pointers up the chain until it hits the root. To merge two sets, you just find their respective roots and point one root to the other.

struct NaiveUnionFind {
    parent: Vec<usize>,
}

impl NaiveUnionFind {
    fn find(&self, i: usize) -> usize {
        if self.parent[i] == i {
            i
        } else {
            self.find(self.parent[i])
        }
    }

    fn union(&mut self, i: usize, j: usize) {
        let root_i = self.find(i);
        let root_j = self.find(j);
        if root_i != root_j {
            self.parent[root_i] = root_j;
        }
    }
}

Here is the problem: this approach doesn't care about the shape of the resulting tree. If you union elements in a specific order—say, 0 with 1, 1 with 2, 2 with 3—you don't get a balanced tree; you get a linked list. Suddenly, your find operation, which you hoped would be nearly instant, becomes O(n). In a real-world scenario with a million elements, you're looking at a stack overflow or a massive performance hit. I've seen this bite people in production when they assume a "simple tree" will stay shallow.

Flattening the hierarchy and balancing the weight

To fix this, we need to move from a naive tree to something that aggressively resists growth. There are two standard tricks here: path compression and union by rank. Path compression is the real magic. Instead of just returning the root during a find call, we update the element's parent to be the root we just found. This effectively "flattens" the tree every time you search, so the next time you look for that element, it's just one step away from the top.

However, path compression alone isn't enough. We also need to ensure that when we merge two trees, we always attach the smaller tree under the root of the larger one. This is where "rank" comes in. By keeping track of the depth (or a proxy for it) of each tree, we prevent the structure from becoming lopsided.

struct UnionFind {
    parent: Vec<usize>,
    rank: Vec<usize>,
}

impl UnionFind {
    fn new(size: usize) -> Self {
        Self {
            parent: (0..size).collect(),
            rank: vec![0; size],
        }
    }

    fn find(&mut self, i: usize) -> usize {
        if self.parent[i] == i {
            i
        } else {
            // Path compression happens here
            let root = self.find(self.parent[i]);
            self.parent[i] = root; 
            root
        }
    }

    fn union(&mut self, i: usize, j: usize) {
        let root_i = self.find(i);
        let root_j = self.find(j);
        
        if root_i != root_j {
            // Union by rank
            if self.rank[root_i] < self.rank[root_j] {
                self.parent[root_i] = root_j;
            } else if self.rank[root_i] > self.rank[root_j] {
                self.parent[root_j] = root_i;
            } else {
                self.parent[root_i] = root_j;
                self.rank[root_j] += 1;
            }
        }
    }
}

Dealing with Rust's borrow checker

You might notice that the find method now requires &mut self. This is because path compression modifies the parent vector during what conceptually feels like a "read" operation. This is a common point of friction in Rust. If you tried to use a pointer-based approach with Rc<RefCell<Node>>, you'd end up with a nightmare of runtime borrows and memory overhead. Using indices into a vector is almost always the right call here; it keeps the data contiguous in memory and lets the borrow checker track mutations clearly.

The trade-off is that you can't easily call find while holding an immutable reference to the UnionFind structure. But given that the time complexity drops from O(n) to nearly O(1) (specifically, the inverse Ackermann function), it's a price I'm more than happy to pay.

📋 Practical Task

Building a Network Partition Detector

You are tasked with building a system that monitors a network of 1,000 servers. Some servers are connected by physical cables. You need to implement a NetworkMonitor struct that uses the optimized Union-Find approach to determine if two servers can communicate (i.e., they belong to the same connected component).

Requirements:

• Implement NetworkMonitor::new(num_servers: usize).
• Implement NetworkMonitor::add_connection(server_a: usize, server_b: usize) which merges the sets containing the two servers.
• Implement NetworkMonitor::is_connected(server_a: usize, server_b: usize) -> bool which returns true if there is a path between the servers.
• Ensure you use both path compression and union by rank to maintain efficiency.

Test Case:

let mut monitor = NetworkMonitor::new(10);
monitor.add_connection(0, 1);
monitor.add_connection(1, 2);
monitor.add_connection(3, 4);
assert!(monitor.is_connected(0, 2)); // Should be true
assert!(!monitor.is_connected(0, 3)); // Should be false
monitor.add_connection(2, 3);
assert!(monitor.is_connected(0, 4)); // Now should be true