algo-union-find-percolation

Answer

Union-Find (Disjoint Set Union)

The implementation provides UnionFind with two key optimizations:

Path compression in Find(): after finding the root, every node along the path is pointed directly to the root. This flattens the tree structure, making subsequent Find() calls nearly O(1).

Weighted union (union by size) in Union(): the smaller tree is always attached under the larger tree. This prevents tall trees, keeping Find() efficient.

// Find returns the root of the component containing p.
// Implements path compression: every node along the path
// is made to point directly to the root.
func (uf *UnionFind) Find(p int) int {
    if p < 0 || p >= len(uf.parent) {
        return -1
    }
    // Find root with path compression (iterative)
    root := p
    for root != uf.parent[root] {
        root = uf.parent[root]
    }
    // Path compression: make all nodes on the path point to root
    for p != root {
        next := uf.parent[p]
        uf.parent[p] = root
        p = next
    }
    return root
}

// Union merges the components containing p and q.
// Uses weighted union (by size): the smaller tree is attached
// under the larger tree to keep the tree flat.
func (uf *UnionFind) Union(p, q int) {
    rootP := uf.Find(p)
    rootQ := uf.Find(q)
    if rootP == rootQ {
        return
    }
    if uf.size[rootP] < uf.size[rootQ] {
        uf.parent[rootP] = rootQ
        uf.size[rootQ] += uf.size[rootP]
    } else {
        uf.parent[rootQ] = rootP
        uf.size[rootP] += uf.size[rootQ]
    }
    uf.count--
}

Percolation Problem

The Percolation struct uses two Union-Find data structures to avoid the classic backwash problem:

• uf — has virtual top and bottom nodes. Used for Percolates() to check connectivity from top to bottom.
• ufFull — has only a virtual top node. Used for IsFull() to check if a site connects to the top. Without a virtual bottom, bottom-row sites connected only through the virtual bottom (not via actual open paths) won't be falsely reported as full.

When opening a site: 1. Mark it open 2. Connect to virtual top (if top row) in both UFs 3. Connect to virtual bottom (if bottom row) only in uf (not ufFull) 4. Union with all open neighbors in both UFs