Definition
- Union-Find (DSU) – maintains a collection of disjoint sets with two operations:
find(representative) andunion(merge). - Parent array –
parent[i]points to i's parent; the root points to itself; all elements start as singletons. - Path compression – recursive
findre-points every visited node directly to the root:parent[x] = find(parent[x]). - Union by rank – attach the lower-rank root under the higher-rank root; increment rank only on ties.
- Complexity – amortised inverse Ackermann per operation, at most 4 for any practical input size.
- Applications – Kruskal's MST, cycle detection, connected components, dynamic connectivity.
At National Bank of India, each account points to a family head. The true head points to itself. To check if two accounts share a family, Rajesh walks up each chain to the head. Path compression re-points everyone directly to the head, so repeated checks are instant. Union by rank keeps the chains short by attaching smaller families under larger ones.
Understanding the Concepts
What is Union-Find and when do you need it?
Union-Find, also called Disjoint Set Union (DSU), solves the dynamic connectivity problem: given a sequence of union operations that merge groups, efficiently answer whether two elements are in the same group. It supports two operations: find(x) returns the representative root of the set containing x, and union(x, y) merges the sets of x and y.
package com.bank.core;
public class DSU {
private int[] parent, rank;
public DSU(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public boolean union(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return false;
if (rank[rx] < rank[ry]) parent[rx] = ry;
else if (rank[rx] > rank[ry]) parent[ry] = rx;
else { parent[ry] = rx; rank[rx]++; }
return true;
}
public boolean connected(int x, int y) { return find(x) == find(y); }
public static void main(String[] args) {
DSU dsu = new DSU(6);
dsu.union(0, 1);
dsu.union(2, 3);
dsu.union(4, 5);
System.out.println("0-1: " + dsu.connected(0, 1)); // true
System.out.println("0-3: " + dsu.connected(0, 3)); // false
dsu.union(1, 3);
System.out.println("0-3: " + dsu.connected(0, 3)); // true
}
}
0-1: true
0-3: false
0-3: true
How does path compression work internally?
Path compression happens during find. The recursive form if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; walks to the root and then, as the recursion unwinds, sets every node's parent directly to the root. After one find, the entire chain is flat, so future finds on any of those nodes are O(1).
package com.bank.core;
import java.util.Arrays;
public class PathCompressionDemo {
static int[] parent = {0, 0, 1, 2, 3}; // chain: 4->3->2->1->0
static int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public static void main(String[] args) {
System.out.println("Before find(4): " + Arrays.toString(parent));
find(4);
System.out.println("After find(4): " + Arrays.toString(parent));
}
}
Before find(4): [0, 0, 1, 2, 3]
After find(4): [0, 0, 0, 0, 0]
How does union by rank work?
Union by rank keeps trees shallow. When merging two sets, find both roots. If they have different ranks (upper bounds on height), attach the lower-rank root under the higher-rank root. If they have the same rank, pick one arbitrarily and increment its rank. This ensures the tree height grows only logarithmically.
package com.bank.core;
public class UnionByRankDemo {
private int[] parent, rank;
public UnionByRankDemo(int n) {
parent = new int[n]; rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public void union(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return;
if (rank[rx] < rank[ry]) parent[rx] = ry;
else if (rank[rx] > rank[ry]) parent[ry] = rx;
else { parent[ry] = rx; rank[rx]++; }
System.out.println("union(" + x + "," + y + "): rank of root=" + rank[find(x)]);
}
public static void main(String[] args) {
UnionByRankDemo uf = new UnionByRankDemo(5);
uf.union(0, 1); // rank[0] = 1
uf.union(2, 3); // rank[2] = 1
uf.union(0, 2); // tie, rank[0] = 2
uf.union(0, 4); // rank stays 2
}
}
union(0,1): rank of root=1
union(2,3): rank of root=1
union(0,2): rank of root=2
union(0,4): rank of root=2
What is the time complexity and why?
With both path compression and union by rank, the amortised cost per operation is the inverse Ackermann function, alpha(n). For any realistic input size (up to 10^80), alpha(n) is at most 4. This makes each operation effectively constant time. Either optimisation alone gives O(log n), but together they achieve the tighter bound.
How is Union-Find used in cycle detection?
When building a graph edge by edge, if both endpoints of a new edge already share the same root, adding that edge would create a cycle. Union-Find detects this in near-constant time per edge.
package com.bank.service;
public class GraphCycleDetection {
private int[] parent, rank;
public GraphCycleDetection(int n) {
parent = new int[n]; rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public boolean addEdge(int u, int v) {
int ru = find(u), rv = find(v);
if (ru == rv) return false; // cycle!
if (rank[ru] < rank[rv]) parent[ru] = rv;
else if (rank[ru] > rank[rv]) parent[rv] = ru;
else { parent[rv] = ru; rank[ru]++; }
return true;
}
public static void main(String[] args) {
GraphCycleDetection g = new GraphCycleDetection(4);
System.out.println("Add 0-1: " + g.addEdge(0, 1)); // true
System.out.println("Add 1-2: " + g.addEdge(1, 2)); // true
System.out.println("Add 2-3: " + g.addEdge(2, 3)); // true
System.out.println("Add 3-0: " + g.addEdge(3, 0)); // false (cycle)
}
}
Add 0-1: true
Add 1-2: true
Add 2-3: true
Add 3-0: false
How is Union-Find used in counting connected components?
After processing all edges, the number of connected components equals the number of distinct roots. You can count them by checking how many elements satisfy parent[i] == i (after path compression via find on each element).
package com.bank.core;
public class ConnectedComponents {
private int[] parent, rank;
private int components;
public ConnectedComponents(int n) {
parent = new int[n]; rank = new int[n]; components = n;
for (int i = 0; i < n; i++) parent[i] = i;
}
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public void union(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return;
if (rank[rx] < rank[ry]) parent[rx] = ry;
else if (rank[rx] > rank[ry]) parent[ry] = rx;
else { parent[ry] = rx; rank[rx]++; }
components--;
}
public int getComponents() { return components; }
public static void main(String[] args) {
ConnectedComponents cc = new ConnectedComponents(6);
cc.union(0, 1);
cc.union(2, 3);
cc.union(4, 5);
System.out.println("Components: " + cc.getComponents()); // 3
cc.union(1, 3);
System.out.println("Components: " + cc.getComponents()); // 2
}
}
Components: 3
Components: 2
What are the limitations?
Union-Find is not easily decremental. Once two sets are merged, you cannot efficiently split them apart. It suits problems where sets only grow, like accumulating fraud links. For dynamic split/merge, link-cut trees or rollback-capable DSU are needed.
What is the banking use case?
At National Bank of India, Pankaj uses Union-Find to cluster accounts into fraud rings. Each shared signal (device, phone, transfer) triggers a union. Each risk check is a find-and-compare query. Because path compression keeps the structure flat, queries stay near-instant even as Rajesh's rings grow into the thousands of accounts.
package com.bank.service;
public class AccountCluster {
private int[] parent, rank;
public AccountCluster(int maxAccounts) {
parent = new int[maxAccounts]; rank = new int[maxAccounts];
for (int i = 0; i < maxAccounts; i++) parent[i] = i;
}
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public void link(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return;
if (rank[ra] < rank[rb]) parent[ra] = rb;
else if (rank[ra] > rank[rb]) parent[rb] = ra;
else { parent[rb] = ra; rank[ra]++; }
}
public boolean sameCluster(int a, int b) { return find(a) == find(b); }
public static void main(String[] args) {
AccountCluster ac = new AccountCluster(1000);
ac.link(101, 202); // shared device
ac.link(202, 303); // shared phone
System.out.println("101-303 same cluster: " + ac.sameCluster(101, 303));
System.out.println("101-404 same cluster: " + ac.sameCluster(101, 404));
}
}
101-303 same cluster: true
101-404 same cluster: false
Visual Overview
Union-Find Implementation
═════════════════════════
Initial: parent = [0, 1, 2, 3, 4] (each is its own root)
union(0,1): parent = [0, 0, 2, 3, 4] rank[0]=1
union(2,3): parent = [0, 0, 2, 2, 4] rank[2]=1
union(0,2): parent = [0, 0, 0, 2, 4] rank[0]=2 (tie)
find(3): 3→2→0 (root) path compression → parent = [0, 0, 0, 0, 4]
Path Compression Visualized:
Before: After:
0 0
/ \ / | \
1 2 1 2 3
|
3
Key Takeaway
Implementing Union-Find means building a parent array where every element starts as its own singleton, with find walking parent links to the root and union linking one root under another. Path compression during find re-points every visited node directly to the root, flattening the tree. Union by rank always attaches the shorter tree under the taller one. Together these make each operation effectively constant time.
Union-Find is the backbone of Kruskal's MST, cycle detection, connected components, and dynamic connectivity. Its one limitation is that it cannot efficiently split merged sets, so it suits problems where groups only grow.
In the banking project at National Bank of India, Pankaj uses this to cluster accounts into fraud rings. Each shared signal triggers a union, each risk check is a find-and-compare, and path compression keeps queries near-instant even with thousands of accounts in a ring.
Remember one sentence: implement find with parent[x] = find(parent[x]) for path compression, and union by linking the lower-rank root under the higher, for effectively O(1) amortised disjoint set operations.
---