Definition
- Union-Find (Disjoint Set Union) – a data structure that maintains a partition of elements into non-overlapping sets.
- find(x) – returns the representative root of the set containing x by following parent links to the element that points to itself.
- union(x, y) – merges the sets containing x and y by linking one root under the other.
- Path compression – during find, re-point every node on the path directly to the root, flattening the tree.
- Union by rank – attach the shorter tree under the taller one; only increment rank when two equal-rank trees merge.
- Complexity – amortised inverse Ackermann per operation, which is at most 4 for any practical input.
At National Bank of India, fraud analysts group accounts into related-party clusters. Each account points to a head account, and the true head points to itself. To check whether two accounts are in the same cluster, Rajesh walks up to each account's head and compares. Path compression re-points everyone directly to the head once discovered, so repeated checks are almost instant.
Understanding the Concepts
What is Union-Find?
Union-Find, also called Disjoint Set Union (DSU), maintains a collection of disjoint sets and supports two operations: find returns a representative root identifying which set an element belongs to, and union merges the sets of two elements. Two elements are in the same set exactly when they share the same root.
package com.bank.core;
public 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;
}
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]); // path compression
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]++; }
}
public boolean connected(int x, int y) {
return find(x) == find(y);
}
public static void main(String[] args) {
UnionFind uf = new UnionFind(5);
uf.union(0, 1);
uf.union(2, 3);
System.out.println("0 and 1 connected: " + uf.connected(0, 1)); // true
System.out.println("0 and 2 connected: " + uf.connected(0, 2)); // false
uf.union(1, 3);
System.out.println("0 and 2 connected: " + uf.connected(0, 2)); // true
}
}
0 and 1 connected: true
0 and 2 connected: false
0 and 2 connected: true
How does the parent array work?
The structure is backed by a parent[] array where parent[i] is the element that i points to. Initially, every element is its own parent, meaning every element is a singleton set. The representative of a set is its root: the element where parent[x] == x.
To find the root, you follow parent links until you reach an element that points to itself. Without optimisations, this chain can be long. Path compression and union by rank keep it short.
package com.bank.core;
public class ParentArrayDemo {
public static void main(String[] args) {
int[] parent = {0, 1, 2, 3, 4}; // initial: each is its own root
System.out.println("Initial parent: ");
for (int i = 0; i < parent.length; i++)
System.out.println(" parent[" + i + "] = " + parent[i]);
// union(1, 0): point 1's root to 0's root
parent[1] = 0;
// union(2, 0): point 2's root to 0's root
parent[2] = 0;
System.out.println("After unions:");
for (int i = 0; i < parent.length; i++)
System.out.println(" parent[" + i + "] = " + parent[i]);
}
}
Initial parent:
parent[0] = 0
parent[1] = 1
parent[2] = 2
parent[3] = 3
parent[4] = 4
After unions:
parent[0] = 0
parent[1] = 0
parent[2] = 0
parent[3] = 3
parent[4] = 4
How does path compression work?
Path compression rewrites the chain during find so every node on the path points directly to the root. The clean recursive form is: if (parent[x] != x) parent[x] = find(parent[x]); return parent[x];. This sets each node's parent to the root as the recursion unwinds, flattening the tree for all future lookups.
package com.bank.core;
import java.util.Arrays;
public class PathCompression {
private static int[] parent = {0, 0, 1, 2, 3}; // chain: 4->3->2->1->0
public 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: " + Arrays.toString(parent));
System.out.println("find(4) = " + find(4));
System.out.println("After: " + Arrays.toString(parent));
// All nodes now point directly to root 0
}
}
Before: [0, 0, 1, 2, 3]
find(4) = 0
After: [0, 0, 0, 0, 0]
How does union by rank work?
Union by rank keeps trees shallow by always attaching the tree with the smaller rank under the one with larger rank. Rank is an upper bound on tree height. Only when two trees have equal rank does the rank increase by one.
package com.bank.core;
public class UnionByRank {
private int[] parent, rank;
public UnionByRank(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]++; }
}
public static void main(String[] args) {
UnionByRank uf = new UnionByRank(6);
uf.union(0, 1); // rank[0] becomes 1
uf.union(2, 3); // rank[2] becomes 1
uf.union(0, 2); // rank[0] becomes 2 (tie)
uf.union(4, 5);
uf.union(0, 4); // rank[0] stays 2 (4's tree is shorter)
System.out.println("All in same set: " + (uf.find(0) == uf.find(5)));
}
}
All in same set: true
What is the time complexity?
With both path compression and union by rank, the amortised cost per operation is the inverse Ackermann function, written as alpha(n). This function grows so slowly that for any practical input (up to 10^80 elements), alpha(n) is at most 4. This means each find and union is effectively constant time.
Either optimisation alone is weaker. Path compression alone gives O(log n) amortised. Union by rank alone gives O(log n) worst case. Together they achieve the inverse Ackermann bound.
When is Union-Find used?
Union-Find is the backbone of several classic algorithms and applications:
- Kruskal's Minimum Spanning Tree : process edges in weight order, union endpoints, skip if already connected.
- Cycle detection : while building a graph, if union finds both endpoints already share a root, the edge creates a cycle.
- Connected components : union adjacent elements and count distinct roots.
- Dynamic connectivity : answer whether two elements are connected after a sequence of union operations.
package com.bank.service;
public class CycleDetection {
private int[] parent, rank;
public CycleDetection(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; // cycle detected
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 static void main(String[] args) {
CycleDetection cd = new CycleDetection(4);
System.out.println("Add 0-1: " + cd.union(0, 1)); // true
System.out.println("Add 1-2: " + cd.union(1, 2)); // true
System.out.println("Add 2-0: " + cd.union(2, 0)); // false: cycle!
}
}
Add 0-1: true
Add 1-2: true
Add 2-0: false
What are the limitations?
Union-Find is not easily decremental. Once two sets are merged, you cannot efficiently split them apart. This means it suits problems where sets only ever grow, such as accumulating fraud links. If you need to remove connections, other data structures like link-cut trees are needed.
What is the banking use case?
At National Bank of India, Pankaj the architect uses Union-Find to cluster accounts into fraud rings. When the team discovers a link between two accounts, such as a shared device or phone number, Rajesh calls union to merge their groups. When Priya queries whether two accounts belong to the same ring, the system calls find on both and compares the roots. Because the structure stays flat after path compression, these queries are near-instant even as rings grow into the thousands.
package com.bank.service;
public class FraudRingCluster {
private int[] parent, rank;
public FraudRingCluster(int numAccounts) {
parent = new int[numAccounts];
rank = new int[numAccounts];
for (int i = 0; i < numAccounts; i++) parent[i] = i;
}
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public void linkAccounts(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 sameRing(int a, int b) {
return find(a) == find(b);
}
public static void main(String[] args) {
FraudRingCluster cluster = new FraudRingCluster(100);
cluster.linkAccounts(10, 25); // shared device
cluster.linkAccounts(25, 42); // shared phone
System.out.println("10 and 42 in same ring: " + cluster.sameRing(10, 42)); // true
System.out.println("10 and 50 in same ring: " + cluster.sameRing(10, 50)); // false
}
}
10 and 42 in same ring: true
10 and 50 in same ring: false
Visual Overview
Union-Find: Path Compression
═════════════════════════════
Before find(4): After find(4):
0 0
│ / | \
1 1 2 3
│ \
2 4
│
3 All nodes point
│ directly to root 0
4
Union by Rank:
══════════════
Tree A (rank 2) Tree B (rank 1)
0 3
/ \ |
1 2 4
union(A, B) → attach shorter (B) under taller (A):
0
/ | \
1 2 3
|
4
Key Takeaway
Union-Find, or Disjoint Set Union, maintains a collection of disjoint sets and supports two operations: find returns a representative root identifying which set an element belongs to, and union merges the sets of two elements. The data structure is backed by a parent array where every element initially points to itself. Two elements are in the same set when they share the same root.
The power comes from two optimisations. Path compression flattens the tree during find by re-pointing every visited node directly to the root. Union by rank attaches the shorter tree under the taller one and only bumps the rank when two equal-height trees merge. Together they give inverse Ackermann amortised time, which is effectively constant for any practical input.
Union-Find powers Kruskal's MST, cycle detection, connected components, and dynamic connectivity queries. Its one limitation is that it is not easily decremental: you cannot efficiently split a set once merged, so it fits problems where sets only grow.
In the banking project at National Bank of India, Pankaj uses Union-Find to cluster accounts into fraud rings. When Rajesh discovers a shared device or phone number between accounts, he calls union. When Priya queries whether two accounts are in the same ring, the system calls find on both and compares roots, near-instantly even as rings grow large.
Remember one sentence: path compression plus union by rank give near-constant amortised time for disjoint set operations.
---