Union-Find Data Structure: Implementation, Optimizations, and Use Cases

The Union-Find data structure (并查集) maintains dynamic disjoint sets with practically constant-time union and connectivity queries using path compression and union-by-size optimizations.

The labuladong/fucking-algorithm repository provides production-ready implementations of this essential algorithmic tool across Java, C++, and Go. By representing each subset as a tree and applying two critical optimizations, Union-Find achieves an amortized time complexity of O(α(N))—effectively constant—for all core operations.

Core Operations and Optimizations

Union-Find tracks a collection of elements partitioned into disjoint subsets using a parent array where each node points to its parent, and root nodes point to themselves. The structure supports three primary methods:

• find(x): Locates the root of the component containing x.
• union(p, q): Merges the components containing p and q.
• connected(p, q): Returns true if p and q share the same root.

Two optimizations ensure tree heights remain minimal:

1. Path Compression: During find(x), every visited node is rewired to point directly to the root, flattening the tree structure.
2. Union-by-Size: When merging two trees, the smaller tree is always attached under the larger tree’s root, preventing degenerate chains.

According to the analysis in 算法思维系列/UnionFind算法详解.md, these techniques yield an amortized complexity of O(α(N)) per operation, where α is the inverse Ackermann function—smaller than 5 for all practical values of N.

Java Implementation

The reference Java implementation from 算法思维系列/UnionFind算法详解.md (lines 40-66) demonstrates the complete class structure with size tracking and path compression:

class UF {
    private int count;          // number of components
    private int[] parent;       // parent[i] = parent of i
    private int[] size;         // size of component for roots (used for weighting)

    public UF(int n) {
        count = n;
        parent = new int[n];
        size   = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i]   = 1;
        }
    }

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

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return;

        // union‑by‑size
        if (size[rootP] < size[rootQ]) {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        } else {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        }
        count--;
    }

    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    public int count() { return count; }
}

This implementation maintains a count field that decrements with each successful union, enabling O(1) retrieval of the current number of connected components.

Go Implementation

For Go developers, the repository provides an equivalent implementation in 多语言解法代码/solution_code.md (lines 14423-14448). The structure uses pointer receivers for efficient state modification:

type UF struct {
    count  int
    parent []int
    size   []int
}

func NewUF(n int) *UF {
    uf := &UF{count: n, parent: make([]int, n), size: make([]int, n)}
    for i := 0; i < n; i++ {
        uf.parent[i] = i
        uf.size[i]   = 1
    }
    return uf
}

func (uf *UF) find(x int) int {
    for uf.parent[x] != x {
        uf.parent[x] = uf.parent[uf.parent[x]] // path compression
        x = uf.parent[x]
    }
    return x
}

func (uf *UF) union(p, q int) {
    rootP, rootQ := uf.find(p), uf.find(q)
    if rootP == rootQ { return }
    if uf.size[rootP] > uf.size[rootQ] {
        uf.parent[rootQ] = rootP
        uf.size[rootP] += uf.size[rootQ]
    } else {
        uf.parent[rootP] = rootQ
        uf.size[rootQ] += uf.size[rootP]
    }
    uf.count--
}

func (uf *UF) connected(p, q int) bool { return uf.find(p) == uf.find(q) }
func (uf *UF) Count() int               { return uf.count }

Both implementations are available in 多语言解法代码/solution_code.md alongside C++ variants (lines 14367-14420), demonstrating cross-language consistency in algorithm design.

Key Use Cases

Dynamic Connectivity

Union-Find excels in online graph scenarios where edges are incrementally added and the system must answer connectivity queries ("are vertices u and v connected?"). Each new edge triggers union(u, v), while queries use connected(u, v).

Kruskal's Minimum Spanning Tree

In Kruskal's algorithm, Union-Find provides the cycle detection mechanism required to build an MST. After sorting edges by weight, the algorithm tests connected(u, v); if false, it adds the edge and calls union(u, v).

Counting Connected Components

For problems like "Number of Islands" or "Friend Circles," Union-Find offers an alternative to DFS/BFS. As detailed in 高频面试系列/岛屿题目.md (line 88), grid coordinates map to 1-D indices, adjacent land cells trigger union operations, and the final count() reveals the number of distinct islands.

Equivalence Relations

Union-Find efficiently solves equation satisfaction problems (e.g., LeetCode 990). Each variable becomes a node, equality equations become union operations, and inequality assertions are validated via connected checks.

Practical Example: Connecting Nodes with Minimum Cost

The solution for LeetCode 1135 ("Minimum Cost to Connect All Points") in 多语言解法代码/solution_code.md (lines 14520-14540) demonstrates Union-Find within Kruskal's algorithm:

public int minimumCost(int n, int[][] connections) {
    UF uf = new UF(n + 1);                     // 1‑based node ids
    Arrays.sort(connections, (a, b) -> a[2] - b[2]); // sort by weight
    int mst = 0;
    for (int[] e : connections) {
        int u = e[0], v = e[1], w = e[2];
        if (!uf.connected(u, v)) {             // no cycle
            uf.union(u, v);
            mst += w;
        }
    }
    return uf.count() == 2 ? mst : -1;          // count==2 because node 0 is unused
}

This pattern—sorting edges by weight then using connected to detect cycles—generalizes to any MST implementation requiring efficient component management.

Summary

• Union-Find maintains disjoint sets using a parent array with path compression and union-by-size optimizations, achieving O(α(N)) amortized time per operation.
• The labuladong/fucking-algorithm repository provides canonical implementations in 算法思维系列/UnionFind算法详解.md (conceptual explanation) and 多语言解法代码/solution_code.md (production code in Java/C++/Go).
• Core methods include find(x) for root lookup, union(p,q) for merging components, connected(p,q) for connectivity testing, and count() for component enumeration.
• Primary applications include dynamic connectivity, Kruskal's MST, island counting (as explored in 高频面试系列/岛屿题目.md), and equation satisfiability problems.

Frequently Asked Questions

What is the time complexity of Union-Find operations?

With path compression and union-by-size, both union and find operations run in O(α(N)) amortized time, where α is the inverse Ackermann function. This grows so slowly that it is effectively a small constant (≤ 4) for all practical input sizes.

How does path compression optimize the Union-Find data structure?

During the find(x) operation, path compression flattens the tree structure by making every visited node point directly to the root node. This ensures that subsequent queries on those nodes execute in nearly constant time, preventing the degradation that would occur in deep, unbalanced trees.

Why use Union-Find instead of BFS or DFS for connectivity problems?

Use Union-Find when the graph is dynamic and only supports edge additions (incremental connectivity), as it answers queries in near-constant time without traversing the entire graph. Use BFS or DFS when you need the actual path between nodes, when edges can be deleted, or when memory usage must remain linear without the overhead of maintaining parent and size arrays.

Can Union-Find handle directed graphs or edge weights?

Union-Find treats edges as undirected connections for component grouping; it does not preserve directionality. While the structure itself ignores edge weights, it serves as the foundation for Kruskal's algorithm by handling connectivity checks after edges are externally sorted by weight. For weighted directed graphs requiring shortest paths, algorithms like Dijkstra or Bellman-Ford are more appropriate.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}