These are the notes for DSA episode 55. Some graph questions don't need a path at all, only: are these two already connected? When that question is asked lakhs of times while edges keep arriving, a DFS every time is far too slow. We start from a real-life problem (a telecom company laying fibre cables), define every word, try the obvious idea (a DFS before every cable: correct, but Time Limit Exceeded on a hub town with 2 lakh cables), find the key insight (every group has a leader; find follows parent pointers to it, union links two leaders), see why the first version is still slow (tall chains), and fix it with union by size and path compression: almost O(1) per operation. Every program below was run with javac 21 with an 8-second limit (like the SyntaxPilot compiler), and every output shown is real.
The problem, in real life
A telecom company lays fibre cables between towns, one cable at a time. As cables go in, towns join into groups; inside a group a signal reaches every town. Before every new cable the planner asks: are these two towns already connected? If yes, the cable is wasted money. The question is asked before every single cable, lakhs of times.
| With the cables | In code |
|---|---|
| A town | a vertex |
| A cable | an undirected edge [a, b] |
| A group of connected towns | a connected component (a set) |
| The group's leader | the root (parent[r] == r) |
| "Who is your leader?" | find(x) |
| Two groups merge | union(a, b) |
| A wasted cable | a redundant edge: find(a) == find(b) before adding |
Every word, from zero
- Connected component: a group of vertices where everyone can reach everyone.
- Disjoint sets: groups that never share a member; every vertex is in exactly one.
- Parent pointer: each vertex stores one other vertex,
parent[x]; following them leads to the root. - Root (leader, representative): the vertex whose parent is itself; it names the group.
find(x): follow parents fromxto the root.union(a, b): find both roots; if different, point one root at the other.- Union by size: keep
size[root]; always hang the smaller group under the bigger one's root. Trees stay aboutlog ntall. - Path compression: after
findreaches the root, point every vertex on the way directly at the root. - Redundant edge: an edge between two vertices that are already connected; it closes a cycle.
- Inverse Ackermann function α(n): the cost per operation with both tricks; it grows so slowly that it is at most 4 for any realistic
n.
Problem statements
LeetCode 684, Redundant Connection. A tree with n nodes 1..n got one extra edge. edges lists n edges; return the edge that can be removed so the rest is a tree (if several, the last one in the input, which is the first one that closes a cycle when we add them in order).
| edges | Answer |
|---|---|
[[1,2],[1,3],[2,3]] |
[2,3] |
[[1,2],[2,3],[3,4],[1,4],[1,5]] |
[1,4] |
LeetCode 547, Number of Provinces. isConnected[i][j] = 1 if cities i and j are directly connected. A province is a group of directly or indirectly connected cities. Return the number of provinces.
| isConnected | Answer |
|---|---|
[[1,1,0],[1,1,0],[0,0,1]] |
2 |
[[1,0,0],[0,1,0],[0,0,1]] |
3 |
Constraints: 684: 3 ≤ n ≤ 1000; 547: 1 ≤ n ≤ 200. We also test a bigger network of 2 lakh towns.
Obvious idea: a DFS before every cable
Keep the graph built so far. Before adding u - v, run a DFS from u; if it reaches v, the edge is redundant.
import java.util.*;
public class Main {
static int[] findRedundantConnection(int[][] edges) {
int n = edges.length;
List<List<Integer>> adj = new ArrayList<>();
for (int v = 0; v <= n; v++) adj.add(new ArrayList<>());
for (int[] e : edges) {
if (connected(adj, e[0], e[1], n)) return e;
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
return new int[0];
}
static boolean connected(List<List<Integer>> adj, int s, int t, int n) {
boolean[] seen = new boolean[n + 1];
Deque<Integer> stack = new ArrayDeque<>();
stack.push(s);
seen[s] = true;
while (!stack.isEmpty()) {
int u = stack.pop();
if (u == t) return true;
for (int v : adj.get(u))
if (!seen[v]) { seen[v] = true; stack.push(v); }
}
return false;
}
public static void main(String[] args) {
int[][] ex1 = {{1, 2}, {1, 3}, {2, 3}};
int[][] ex2 = {{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}};
System.out.println(Arrays.toString(findRedundantConnection(ex1)));
System.out.println(Arrays.toString(findRedundantConnection(ex2)));
}
}
[2, 3]
[1, 4]
Correct. Now a hub town (town 1) cabled to 2 lakh other towns, then one last cable 2 - 3:
import java.util.*;
public class Main {
static int[] findRedundantConnection(int[][] edges) {
int n = edges.length;
List<List<Integer>> adj = new ArrayList<>();
for (int v = 0; v <= n; v++) adj.add(new ArrayList<>());
for (int[] e : edges) {
if (connected(adj, e[0], e[1], n)) return e;
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
return new int[0];
}
static boolean connected(List<List<Integer>> adj, int s, int t, int n) {
boolean[] seen = new boolean[n + 1];
Deque<Integer> stack = new ArrayDeque<>();
stack.push(s);
seen[s] = true;
while (!stack.isEmpty()) {
int u = stack.pop();
if (u == t) return true;
for (int v : adj.get(u))
if (!seen[v]) { seen[v] = true; stack.push(v); }
}
return false;
}
public static void main(String[] args) {
int n = 200000;
int[][] edges = new int[n][];
for (int i = 0; i < n - 1; i++) edges[i] = new int[]{1, i + 2};
edges[n - 1] = new int[]{2, 3};
long t0 = System.nanoTime();
int[] e = findRedundantConnection(edges);
System.out.println(Arrays.toString(e) + ", " + (System.nanoTime() - t0) / 1000000 + " ms");
}
}
Time Limit Exceeded (stopped after 8 seconds)
Why it's slow: each DFS walks the whole group around the hub, up to 2 lakh towns: 2 lakh × 2 lakh = 4,000 crore steps. And the waste: we only need same group or not, never the path.
The key insight: every group has a leader
By hand, with five towns:
| Step | Operation | What happens |
|---|---|---|
| 0 | start | every town is its own leader: 5 groups |
| 1 | union(1, 2) |
2's leader points to 1 |
| 2 | union(3, 4) |
4's leader points to 3 |
| 3 | union(2, 4) |
find(2) = 1, find(4) = 3: leader 3 points to 1 |
| 4 | union(1, 4)? |
find(1) = 1, find(4) = 1: same leader, wasted cable |
A first Union-Find
import java.util.*;
public class Main {
static int[] parent;
static int find(int x) {
while (parent[x] != x) x = parent[x];
return x;
}
static boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
parent[ra] = rb;
return true;
}
static int[] findRedundantConnection(int[][] edges) {
int n = edges.length;
parent = new int[n + 1];
for (int i = 0; i <= n; i++) parent[i] = i;
for (int[] e : edges)
if (!union(e[0], e[1])) return e;
return new int[0];
}
public static void main(String[] args) {
int[][] ex1 = {{1, 2}, {1, 3}, {2, 3}};
int[][] ex2 = {{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}};
System.out.println(Arrays.toString(findRedundantConnection(ex1)));
System.out.println(Arrays.toString(findRedundantConnection(ex2)));
}
}
[2, 3]
[1, 4]
Correct, but on the 2 lakh hub towns:
Time Limit Exceeded (stopped after 8 seconds)
Why it's still slow: union(1, 2) makes 1 point to 2; union(1, 3): find(1) = 2, so 2 points to 3; then 3 points to 4… The parents form one long chain, and every new cable starts with find(1), which walks the whole chain: O(n²) again.
The two fixes
- Union by size: keep the size of every group; hang the smaller root under the bigger one. A tree's height can then only grow when its group at least doubles, so it stays ≤ log₂ n.
- Path compression:
parent[x] = find(parent[x]): after onefind, everyone on the path points straight at the root, so the nextfindis one step.
The optimal solution in Java: union by size + path compression
static int[] parent, size;
static void init(int n) {
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
}
static int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
static boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
parent[rb] = ra;
size[ra] += size[rb];
return true;
}
Redundant connection (towns 1..n, so init(n + 1)):
static int[] findRedundantConnection(int[][] edges) {
init(edges.length + 1);
for (int[] e : edges)
if (!union(e[0], e[1])) return e;
return new int[0];
}
Tests: the examples and two cables between the same pair:
[2, 3]
[1, 4]
[2, 1]
The 2 lakh hub towns that timed out twice:
[2, 3], 7 ms
Number of provinces with the same Union-Find: start with n groups; every successful union merges two, so the count drops by one.
import java.util.*;
public class Main {
static int[] parent, size;
static void init(int n) {
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
}
static int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
static boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
parent[rb] = ra;
size[ra] += size[rb];
return true;
}
static int findCircleNum(int[][] isConnected) {
int n = isConnected.length, count = n;
init(n);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (isConnected[i][j] == 1 && union(i, j)) count--;
return count;
}
public static void main(String[] args) {
System.out.println(findCircleNum(new int[][]{{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}));
System.out.println(findCircleNum(new int[][]{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}));
System.out.println(findCircleNum(new int[][]{{1, 1, 1}, {1, 1, 1}, {1, 1, 1}}));
}
}
2
3
1
The same solution in C++
#include <bits/stdc++.h>
using namespace std;
// Union-Find with union by size and path compression; Redundant Connection (684) and Number of Provinces (547).
struct DSU {
vector<int> parent, sz;
DSU(int n) : parent(n), sz(n, 1) { iota(parent.begin(), parent.end(), 0); }
int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
bool unite(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false; // same leader: already connected
if (sz[ra] < sz[rb]) swap(ra, rb); // the smaller group goes under the bigger one
parent[rb] = ra;
sz[ra] += sz[rb];
return true;
}
};
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
DSU d(edges.size() + 1); // towns are 1..n
for (auto& e : edges)
if (!d.unite(e[0], e[1])) return e;
return {};
}
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size(), count = n;
DSU d(n);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (isConnected[i][j] && d.unite(i, j)) count--;
return count;
}
int main() {
vector<vector<int>> e1 = {{1, 2}, {1, 3}, {2, 3}}, e2 = {{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}};
for (auto* e : {&e1, &e2}) { auto r = findRedundantConnection(*e); cout << "[" << r[0] << ", " << r[1] << "]\n"; }
vector<vector<int>> m1 = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}, m2 = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
cout << findCircleNum(m1) << "\n" << findCircleNum(m2) << "\n";
}
[2, 3]
[1, 4]
2
3
The same solution in Python
find is written with a loop here: Python's recursion limit is 1000, and an iterative find with path compression never hits it.
# Union-Find with union by size and path compression; Redundant Connection (684) and Number of Provinces (547).
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
root = x
while self.parent[root] != root: # walk up to the leader
root = self.parent[root]
while self.parent[x] != root: # path compression: point everyone on the way at the leader
self.parent[x], x = root, self.parent[x]
return root
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False # same leader: already connected
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra # the smaller group goes under the bigger one
self.parent[rb] = ra
self.size[ra] += self.size[rb]
return True
def find_redundant_connection(edges):
d = DSU(len(edges) + 1) # towns are 1..n
for a, b in edges:
if not d.union(a, b):
return [a, b]
return []
def find_circle_num(is_connected):
n = len(is_connected)
d, count = DSU(n), n
for i in range(n):
for j in range(i + 1, n):
if is_connected[i][j] and d.union(i, j):
count -= 1
return count
print(find_redundant_connection([[1, 2], [1, 3], [2, 3]]))
print(find_redundant_connection([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]))
print(find_circle_num([[1, 1, 0], [1, 1, 0], [0, 0, 1]]))
print(find_circle_num([[1, 0, 0], [0, 1, 0], [0, 0, 1]]))
[2, 3]
[1, 4]
2
3
Three real bugs
Bug 1: linking the towns, not their roots (parent[a] = b)
import java.util.*;
public class Main {
static int[] parent, size;
static void init(int n) {
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
}
static int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
static boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
parent[a] = b;
return true;
}
static int findCircleNum(int[][] isConnected) {
int n = isConnected.length, count = n;
init(n);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (isConnected[i][j] == 1 && union(i, j)) count--;
return count;
}
public static void main(String[] args) {
System.out.println(findCircleNum(new int[][]{{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}));
System.out.println(findCircleNum(new int[][]{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}));
System.out.println(findCircleNum(new int[][]{{1, 1, 1}, {1, 1, 1}, {1, 1, 1}}));
}
}
2
3
0
0 provinces for three fully connected cities (should be 1). parent[a] = b overwrites a's old link, which can cut a off from its group, and the counting breaks. Fix: always link root to root: parent[rb] = ra.
Bug 2: comparing parents instead of roots
The last test is the five-town picture from the hand trace: [1,2], [3,4], [2,4], [1,4].
import java.util.*;
public class Main {
static int[] parent, size;
static void init(int n) {
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
}
static int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
static boolean union(int a, int b) {
int ra = parent[a], rb = parent[b];
if (ra == rb) return false;
if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
parent[rb] = ra;
size[ra] += size[rb];
return true;
}
static int[] findRedundantConnection(int[][] edges) {
init(edges.length + 1);
for (int[] e : edges)
if (!union(e[0], e[1])) return e;
return new int[0];
}
public static void main(String[] args) {
int[][] ex1 = {{1, 2}, {1, 3}, {2, 3}};
int[][] ex2 = {{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}};
System.out.println(Arrays.toString(findRedundantConnection(ex1)));
System.out.println(Arrays.toString(findRedundantConnection(ex2)));
int[][] ex3 = {{1, 2}, {3, 4}, {2, 4}, {1, 4}};
System.out.println(Arrays.toString(findRedundantConnection(ex3)));
}
}
[2, 3]
[1, 4]
[]
The cycle is missed ([] instead of [1, 4]): town 4's parent is 3 and town 1's parent is 1. Same group, different parents. Only find gives the leader.
Bug 3: an array of size n for towns 1..n
import java.util.*;
public class Main {
static int[] parent, size;
static void init(int n) {
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
}
static int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
static boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
parent[rb] = ra;
size[ra] += size[rb];
return true;
}
static int[] findRedundantConnection(int[][] edges) {
init(edges.length);
for (int[] e : edges)
if (!union(e[0], e[1])) return e;
return new int[0];
}
public static void main(String[] args) {
int[][] ex1 = {{1, 2}, {1, 3}, {2, 3}};
int[][] ex2 = {{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}};
System.out.println(Arrays.toString(findRedundantConnection(ex1)));
System.out.println(Arrays.toString(findRedundantConnection(ex2)));
}
}
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3
at Main.find(Main.java:11)
at Main.union(Main.java:15)
at Main.findRedundantConnection(Main.java:25)
at Main.main(Main.java:31)
Town 3 needs index 3, so the arrays need n + 1 slots: init(edges.length + 1).
Complexity
| Approach | Time | Space | Test |
|---|---|---|---|
| DFS before every edge | O(E × (V + E)) | O(V + E) | 2 lakh towns: Time Limit Exceeded |
| Naive Union-Find | O(E × V) worst case | O(V) | 2 lakh towns: Time Limit Exceeded |
| Union by size only | O(E log V) | O(V) | fast |
| Union by size + path compression | O(E × α(V)), α ≤ 4 | O(V) | 2 lakh towns: a few ms |
| BFS/DFS once (static graph, 547) | O(V + E) | O(V + E) | fine when edges don't arrive one by one |
Union-Find shines when edges arrive over time and you ask "connected?" after each one. For a fixed graph counted once, a single DFS (episode 47) is just as good.
Common mistakes
| Mistake | What you see (real) | Why | Fix |
|---|---|---|---|
| DFS before every edge | Time Limit Exceeded | walks the group every time | Union-Find |
parent[a] = b |
0 provinces |
links towns, not roots | parent[rb] = ra |
parent[a] == parent[b] |
[] (cycle missed) |
a parent is not the leader | find(a) == find(b) |
init(n) for towns 1..n |
ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3 |
index n needed |
init(n + 1) |
| No size/rank and no compression | Time Limit on chains | trees become chains | both tricks |
Recursive find in Python on a chain |
RecursionError |
recursion limit 1000 | iterative find |
Mini project: the cable planner
Lay six cables between Madhya Pradesh towns in order; print each as a new link or WASTED, the number of groups after each, and the final groups.
import java.util.*;
public class Main {
// Mini project: the cable planner. Lay cables in order; report each one as new or wasted, and the groups at the end.
static int[] parent, size;
static int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; }
static boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
parent[rb] = ra; size[ra] += size[rb];
return true;
}
public static void main(String[] args) {
String[] town = {"Indore", "Bhopal", "Ujjain", "Dewas", "Sagar", "Rewa"};
int[][] cables = {{0, 2}, {1, 4}, {0, 3}, {2, 3}, {4, 5}, {1, 5}};
int n = town.length, groups = n;
parent = new int[n]; size = new int[n];
for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
for (int[] c : cables) {
boolean joined = union(c[0], c[1]);
if (joined) groups--;
System.out.printf("%-7s - %-7s %s (groups: %d)%n", town[c[0]], town[c[1]], joined ? "new link" : "WASTED ", groups);
}
Map<Integer, List<String>> byLeader = new TreeMap<>();
for (int i = 0; i < n; i++) byLeader.computeIfAbsent(find(i), k -> new ArrayList<>()).add(town[i]);
System.out.println("Groups: " + byLeader.values());
}
}
Indore - Ujjain new link (groups: 5)
Bhopal - Sagar new link (groups: 4)
Indore - Dewas new link (groups: 3)
Ujjain - Dewas WASTED (groups: 3)
Sagar - Rewa new link (groups: 2)
Bhopal - Rewa WASTED (groups: 2)
Groups: [[Indore, Ujjain, Dewas], [Bhopal, Sagar, Rewa]]
Practice
1. Number of Operations to Make Network Connected (LeetCode 1319).
Solution
A connected network of n computers needs n - 1 cables. If there are fewer, it's impossible (-1). Otherwise count the groups; wasted cables can be moved, and groups - 1 moves join everything.
import java.util.*;
public class Main {
// Number of Operations to Make Network Connected (LeetCode 1319): need n - 1 cables; extra (wasted) cables can be moved.
static int[] parent;
static int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; }
static int makeConnected(int n, int[][] connections) {
if (connections.length < n - 1) return -1; // not enough cables at all
parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
int groups = n;
for (int[] c : connections) {
int a = find(c[0]), b = find(c[1]);
if (a != b) { parent[a] = b; groups--; }
}
return groups - 1; // join the groups with groups - 1 moved cables
}
public static void main(String[] args) {
System.out.println(makeConnected(4, new int[][]{{0, 1}, {0, 2}, {1, 2}}));
System.out.println(makeConnected(6, new int[][]{{0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 3}}));
System.out.println(makeConnected(6, new int[][]{{0, 1}, {0, 2}, {0, 3}, {1, 2}}));
}
}
1
2
-1
2. Accounts Merge (LeetCode 721).
Solution
Union-Find over emails (a HashMap as the parent array): every email in an account is unioned with that account's first email. Then group emails by their leader.
import java.util.*;
public class Main {
// Accounts Merge (LeetCode 721): union all emails of one account; then group emails by leader.
static Map<String, String> parent = new HashMap<>();
static String find(String x) {
parent.putIfAbsent(x, x);
if (!parent.get(x).equals(x)) parent.put(x, find(parent.get(x)));
return parent.get(x);
}
public static void main(String[] args) {
List<List<String>> accounts = List.of(
List.of("John", "johnsmith@mail.com", "john_newyork@mail.com"),
List.of("John", "johnsmith@mail.com", "john00@mail.com"),
List.of("Mary", "mary@mail.com"),
List.of("John", "johnnybravo@mail.com"));
Map<String, String> owner = new HashMap<>();
for (List<String> acc : accounts)
for (int i = 1; i < acc.size(); i++) {
owner.put(acc.get(i), acc.get(0));
parent.put(find(acc.get(i)), find(acc.get(1))); // union with the account's first email
}
Map<String, TreeSet<String>> groups = new TreeMap<>();
for (String email : owner.keySet()) groups.computeIfAbsent(find(email), k -> new TreeSet<>()).add(email);
List<String> out = new ArrayList<>();
for (TreeSet<String> g : groups.values()) out.add(owner.get(g.first()) + " " + g);
Collections.sort(out);
out.forEach(System.out::println);
}
}
John [john00@mail.com, john_newyork@mail.com, johnsmith@mail.com]
John [johnnybravo@mail.com]
Mary [mary@mail.com]
3. Count the provinces after every new edge.
Solution
import java.util.*;
public class Main {
// Count the provinces after every new edge: start with n, and every successful union removes one.
static int[] parent;
static int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; }
public static void main(String[] args) {
int n = 5, groups = n;
int[][] edges = {{0, 1}, {2, 3}, {1, 0}, {3, 4}, {1, 4}};
parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
for (int[] e : edges) {
int a = find(e[0]), b = find(e[1]);
if (a != b) { parent[a] = b; groups--; }
System.out.println("after " + Arrays.toString(e) + ": " + groups + " provinces");
}
}
}
after [0, 1]: 4 provinces
after [2, 3]: 3 provinces
after [1, 0]: 3 provinces
after [3, 4]: 2 provinces
after [1, 4]: 1 provinces
4. Write union by rank instead of size.
Solution
rank is an upper bound on a tree's height. Hang the lower-rank root under the higher one; only when both ranks are equal does the new root's rank grow by one. Tested on the 2 lakh hub towns:
import java.util.*;
public class Main {
// Union by rank instead of size: rank = an upper bound on the tree height; attach the lower rank under the higher.
static int[] parent, rank;
static int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; }
static boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
parent[rb] = ra;
if (rank[ra] == rank[rb]) rank[ra]++; // two equal heights: the new tree is one taller
return true;
}
public static void main(String[] args) {
int n = 200001;
parent = new int[n]; rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
long t0 = System.nanoTime();
int[] wasted = null;
for (int i = 2; i < n; i++) union(1, i);
if (!union(2, 3)) wasted = new int[]{2, 3};
System.out.println(Arrays.toString(wasted) + ", " + (System.nanoTime() - t0) / 1000000 + " ms");
}
}
[2, 3], 14 ms
Quick quiz
Cables in order: [1,2] [3,4] [2,3] [4,5] [1,4] [5,6]. Which one is redundant? A) [1,4] B) [2,3] C) [4,5] D) [5,6]
Answer
A) [1,4]. After [1,2] [3,4] [2,3] [4,5], towns 1 to 5 are one group, so find(1) == find(4).
Interview questions
- What are the two Union-Find operations?
find(x)returns the leader ofx's group;union(a, b)merges two groups by linking their roots. - Why union by size (or rank)? Without it, unions can build a chain and
findbecomes O(n). - What does path compression do? After a
find, every vertex on the path points directly at the root. - What is the complexity with both? O(α(n)) amortised per operation, where α is the inverse Ackermann function (≤ 4 in practice).
- When is Union-Find better than BFS/DFS? When edges arrive one by one (online) and you query connectivity in between, or for Kruskal's MST (next episode).
- Can Union-Find split a group? No, it only merges. For deletions you need other techniques (for example processing offline in reverse).
- How do you count components? Start at
n, subtract one for each successful union.
Glossary
| Term | Meaning |
|---|---|
| Connected component | A group where everyone can reach everyone |
| Disjoint sets | Groups that never share a member |
| Union-Find / DSU | Structure with find and union over disjoint sets |
| Parent pointer | parent[x], one step towards the root |
| Root (leader) | The vertex with parent[r] == r; names its group |
find(x) |
Follow parents to the root |
union(a, b) |
Link the two roots |
| Union by size | Smaller group goes under the bigger one's root |
| Union by rank | Lower (height bound) tree goes under the higher one |
| Path compression | Point every vertex on a find path at the root |
| Redundant edge | An edge between already-connected vertices |
| Inverse Ackermann α(n) | Grows extremely slowly; ≤ 4 in practice |
Summary
- When you only need same group or not, a DFS per question is wasted work.
- Union-Find: every group has a leader;
findfollows parents,unionlinks two roots. - Union by size + path compression make each operation almost O(1): O(α(n)).
- Redundant connection: the first
unionthat returnsfalse. Provinces:nminus the successful unions. - Watch for: linking towns instead of roots, comparing
parent[]instead offind(), andn + 1slots for 1-based towns. - Next episode: minimum spanning tree with Kruskal (which uses today's Union-Find) and Prim.