28 · Union-Find & Minimum Spanning Trees
#547 Number of Provinces
the problem
In plain words
There are n cities. isConnected[i][j] = 1 means cities i and j are directly connected. A province is a group of cities connected directly or indirectly. Return the number of provinces.
in isConnected = [[1,1,0],[1,1,0],[0,0,1]]
out 2
{0, 1} and {2}.
in isConnected = [[1,0,0],[0,1,0],[0,0,1]]
out 3
- 1 ≤ n ≤ 200
- isConnected[i][i] == 1
- isConnected[i][j] == isConnected[j][i]
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternUnion-Find (DSU)Graph DFS / BFS traversal
Provinces are connected components. Start with n of them; every road between two different components merges two into one.
solutions
From brute force to optimal
Each DFS started from an unvisited city floods one whole province.
- For each city not yet seen: provinces++, DFS to mark its whole province.
- DFS from u scans row u of the matrix for neighbours.
Each city's row of n cells is scanned once.
seen array plus recursion depth up to n.
class Solution { public int findCircleNum(int[][] isConnected) { int n = isConnected.length; boolean[] seen = new boolean[n]; int provinces = 0; for (int i = 0; i < n; i++) { if (seen[i]) continue; provinces++; // i starts a brand-new province dfs(isConnected, i, seen); } return provinces; } private void dfs(int[][] g, int u, boolean[] seen) { seen[u] = true; for (int v = 0; v < g.length; v++) { if (g[u][v] == 1 && !seen[v]) dfs(g, v, seen); } }}Same flooding, with an explicit queue — no recursion depth worries.
- For each unseen city: provinces++, BFS with an
ArrayDeque. - Mark cities seen when enqueued, not when dequeued.
Every matrix cell is read once.
Queue and seen array.
class Solution { public int findCircleNum(int[][] isConnected) { int n = isConnected.length; boolean[] seen = new boolean[n]; ArrayDeque<Integer> queue = new ArrayDeque<>(); int provinces = 0; for (int start = 0; start < n; start++) { if (seen[start]) continue; provinces++; seen[start] = true; queue.offer(start); while (!queue.isEmpty()) { int u = queue.poll(); for (int v = 0; v < n; v++) { if (isConnected[u][v] == 1 && !seen[v]) { seen[v] = true; queue.offer(v); } } } } return provinces; }}count = n; for every road (i < j) union the two cities; each real merge does count--.
- Initialise parent/size; provinces = n.
- For i < j with a road: find both roots.
- Different roots → link by size, provinces--.
n²/2 cells; each road costs an amortized near-constant union. Same practical speed as DFS.
parent and size arrays; no recursion stack beyond log n.
class Solution { private int[] parent, size; private int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; } public int findCircleNum(int[][] isConnected) { int n = isConnected.length; parent = new int[n]; size = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } int provinces = n; // every city alone for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // matrix is symmetric: upper half is enough if (isConnected[i][j] == 0) continue; int ri = find(i), rj = find(j); if (ri == rj) continue; // already same province if (size[ri] < size[rj]) { int t = ri; ri = rj; rj = t; } parent[rj] = ri; size[ri] += size[rj]; provinces--; // two provinces became one } } return provinces; }}Dry run
in the room
How to say it in the interview
talk track
- Restate: "count connected components of an undirected graph given as an adjacency matrix." It's the same as counting islands, but each neighbour scan costs O(n) per city.
- Offer DFS first (simple, O(n²)), then DSU — and say DSU is the better fit if roads arrived one at a time.
- Note the matrix is symmetric, so scanning only j > i halves the work.
traps
- Decrementing the count on every road instead of only when two different roots merge.
what they ask next
Follow-ups
Number of Connected Components in an Undirected Graph (LC 323, Premium)?
Identical idea with an edge list instead of a matrix: count = n, union each edge, return count. It has its own page in this chapter, with a judge.
Roads are added online and you must report the count after each one?
That is exactly what DSU is for: O(α(n)) per road. DFS would have to recount from scratch each time.
before you submit
Edge cases to test
- n = 1 → 1 province.
- Every city connected to every other → 1.
- No roads at all (identity matrix) → n.
- Two cities joined only through a third one still form one province.
practise next
Similar problems
- #200Number of IslandsMediumin Graphs
- #323Number of Connected Components in an Undirected GraphMediumin Union-Find & MSTLeetCode Premium
- #1319Number of Operations to Make Network ConnectedMediumin Union-Find & MST