Graphs
Graph Patterns: Connectivity and Union-Find
May 2026
8 min read
If you are given a stream of edges and need to determine if two nodes are in the same network, running a full DFS/BFS every time is incredibly slow. Union-Find solves this elegantly.
Introduction
The Union-Find (or Disjoint Set) data structure is the ultimate tool for handling dynamic connectivity. Instead of walking through nodes to see if they are connected, Union-Find organizes nodes into tree structures, where each network is represented by a single "root" parent.
Core Optimizations
A naive Union-Find can degrade into a linked list, taking $O(N)$ time per operation. To make it run in near $O(1)$ time, we must implement two critical optimizations:
- Path Compression (in
find): Every time we search for the root of a node, we immediately update that node's parent to point directly to the ultimate root. This flattens the tree structure for all future queries. - Union by Rank (in
unite): When merging two networks, we always attach the shorter tree under the root of the taller tree. This guarantees the overall tree remains balanced.
Implementation
java
class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
public int find(int i) {
if (parent[i] == i) return i;
// Path Compression
return parent[i] = find(parent[i]);
}
public boolean unite(int i, int j) {
int rootI = find(i);
int rootJ = find(j);
if (rootI != rootJ) {
// Union by Rank
if (rank[rootI] < rank[rootJ]) {
parent[rootI] = rootJ;
} else if (rank[rootI] > rank[rootJ]) {
parent[rootJ] = rootI;
} else {
parent[rootJ] = rootI;
rank[rootI]++;
}
return true;
}
return false; // Cycle detected
}
}