Number of Provinces
Problem statement
There are n cities, numbered 0 to n - 1. You get an n × n table isConnected: isConnected[i][j] = 1 means city i and city j have a direct road, and 0 means they don't. The table is symmetric, and every city is marked as connected to itself.
A province is a group of cities that can all reach each other, directly or through other cities, with no road leading out of the group. Return how many provinces there are.
Swap "cities" for servers and "roads" for network links: the question is "how many isolated groups is this network split into?"
Examples
Example 1
Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2
Explanation: Cities 0 and 1 are linked, so they form one province. City 2 has no link to either, so it is a province on its own.

Example 2
Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3
Explanation: Only the diagonal is 1, so no two different cities are linked. Each city is its own province.

Hints
i has an edge to city j when isConnected[i][j] == 1. What is a province in graph terms?Approach
Optimal: Union-find
Intuition
Start by treating every city as its own province, so the count is n. Then read the table: each 1 says two cities are in the same province. If they are currently in different groups, merge the groups — and the count drops by one. When every link has been read, the count is the answer.
A union-find (disjoint-set) keeps these groups. Every city points to a parent, and following parents leads to the group's root. find(x) returns x's root; union(a, b) attaches one root under the other. Because the table is symmetric, we only need to read the part above the diagonal (j > i).
Steps
- Set
parent[i] = i,size[i] = 1for every city, andcount = n. - For each
i, and eachjfromi + 1ton - 1:- If
isConnected[i][j] == 1, callunion(i, j).
- If
- In
union(a, b): find both roots. If they differ, attach the smaller group's root under the larger one and subtract 1 fromcount. - Return
count.
Dry run
isConnected = [[1,1,0],[1,1,0],[0,0,1]], starting count = 3
| pair (i, j) | linked? | action | count |
|---|---|---|---|
| (0, 1) | yes | merge {0} and {1} | 2 |
| (0, 2) | no | — | 2 |
| (1, 2) | no | — | 2 |
Answer: 2. In Example 2 no pair above the diagonal is linked, so the count stays at 3.
Complexity
Time O(n²·α(n)) - We read the upper half of the table, about n²/2 entries. Each 1 we find triggers one union, which does two finds. With path halving and union by size, a find costs α(n), the inverse Ackermann function, which is at most 4 in practice. So this is effectively O(n²), the same as DFS.
Space O(n) - We store one parent and one size per city. No stack or visited list is needed. The input table is not counted.
from typing import List
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
n = len(isConnected)
parent = list(range(n))
size = [1] * n
count = n
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for i in range(n):
for j in range(i + 1, n):
if isConnected[i][j] != 1:
continue
ri, rj = find(i), find(j)
if ri == rj:
continue
if size[ri] < size[rj]:
ri, rj = rj, ri
parent[rj] = ri
size[ri] += size[rj]
count -= 1
return count
if __name__ == "__main__":
print(Solution().findCircleNum([[1, 1, 0], [1, 1, 0], [0, 0, 1]])) # 2
print(Solution().findCircleNum([[1, 0, 0], [0, 1, 0], [0, 0, 1]])) # 3RecapThe whole problem in a few lines, for the night before
- Spot it: count groups of connected cities given an n x n adjacency matrix
- Idea: count connected components: for each unvisited city start a DFS or BFS through connected cities and add one to the count (union-find also works)
- Cost: O(n²) time, O(n) space
- Trap: the input is a matrix of cities, not a grid of islands; each row is one city's connections
Interview follow-ups
Return the cities in each province, not just the count.
With DFS, collect every city you mark during one walk into a list, and add that list to the result when the stack empties. With union-find, group the cities by
find(i)in a dictionary at the end. Time stays O(n²), and the output adds O(n) space.Roads are added one at a time, and you must report the count after each one.
Use union-find. Each new road is one
union, and the count drops by one only when the two cities were in different groups. Each update costs near O(1). Re-running DFS after every road would cost O(n²) each time.There are 1,000,000 cities but only a few roads each. What changes?
Don't store an n × n matrix — it would need a trillion entries. Store the roads as an edge list or adjacency list instead, and run BFS or union-find over the edges. The cost becomes O(n + E), where E is the number of roads, which is tiny compared to n².
Frequently asked questions
It is the same question — count connected groups — on a different input shape. Islands gives a grid, where each cell's neighbours are the four cells around it. Provinces gives an adjacency matrix, where city i's neighbours are the columns with a 1 in row i. Once you see both as graphs, the same DFS, BFS or union-find solves each.
Yes. Replace the stack with a queue (take from the front instead of the back) and keep everything else. It visits the cities in a different order but marks exactly the same ones, with the same O(n²) time and O(n) space.
Many tutorials do, and it's a good habit for sparse graphs. Here it doesn't help: building the list still reads all n² entries, and it costs extra memory. Reading the row directly is simpler. If the same graph will be walked many times, converting once can pay off.
Any entry of the table could be the one link that joins two provinces. So a correct answer has to read every entry, which is n² reads, at least once. Both approaches do exactly that much work.
Counting connected groups is how you check for network partitions or split clusters: "after this link failure, how many isolated groups of nodes do we have?" The matrix form also matches how some tools report connectivity between every pair of hosts. It's a natural next step after Number of Islands in a graph interview.
