SyntaxPilot
Courses/DSA and Coding Problems/Lesson 55
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 55 of 90

Union-Find (DSU): provinces and redundant connection

queued

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 from x to 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 about log n tall.
  • Path compression: after find reaches 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

  1. 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.
  2. Path compression: parent[x] = find(parent[x]): after one find, everyone on the path points straight at the root, so the next find is 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

  1. What are the two Union-Find operations? find(x) returns the leader of x's group; union(a, b) merges two groups by linking their roots.
  2. Why union by size (or rank)? Without it, unions can build a chain and find becomes O(n).
  3. What does path compression do? After a find, every vertex on the path points directly at the root.
  4. What is the complexity with both? O(α(n)) amortised per operation, where α is the inverse Ackermann function (≤ 4 in practice).
  5. 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).
  6. Can Union-Find split a group? No, it only merges. For deletions you need other techniques (for example processing offline in reverse).
  7. 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; find follows parents, union links two roots.
  • Union by size + path compression make each operation almost O(1): O(α(n)).
  • Redundant connection: the first union that returns false. Provinces: n minus the successful unions.
  • Watch for: linking towns instead of roots, comparing parent[] instead of find(), and n + 1 slots for 1-based towns.
  • Next episode: minimum spanning tree with Kruskal (which uses today's Union-Find) and Prim.