Number of Provinces
Count connected groups with union-find — the structure that answers "are these two in the same group?" almost instantly
Problem Statement
isConnected[i][j] = 1 means city i and city j are directly connected. A province is a group of cities connected directly or indirectly. Return how many provinces there are.
Input: [[1,1,0],
[1,1,0],
[0,0,1]]
Output: 2
cities 0 and 1 form one province, city 2 is alone
Input: [[1,0,0],
[0,1,0],
[0,0,1]]
Output: 3
nobody is connectedIntuition
DFS solves this: start at an unvisited city, mark everything reachable, and count how many times you had to start over. That is Number of Islands on an adjacency matrix, and it is a perfectly good answer.
This page uses union-find instead, because the problem is the cleanest introduction to it.
The insight
Union-find (also called disjoint set union) answers one question fast: are these two things in the same group?
Each element points at a parent. Follow the parents up and you reach a root — the group's representative. Two elements are in the same group when they share a root.
find(x) → which group is x in? (walk up to the root)
union(a, b) → merge two groups (point one root at the other)Start with every city as its own group — n groups. Each successful union merges two into one, so decrement a counter. Whatever remains is the number of provinces.
Counting down from n is neater than counting components at the end, and it is the standard way to write this.
Approach
Give every city its own parent
parent[i] = i. n separate groups.
For each connection, union the two cities
Only scan the upper triangle (j > i). The matrix is symmetric, so checking both halves does the same work twice.
Decrement the count only on a real merge
If both cities already share a root, they were already in one province. Nothing merged, so nothing is subtracted.
The Two Optimisations
A naive union-find degrades into a linked list and every find becomes O(n). Two small additions make it effectively O(1).
Path compression
While walking up to the root, point each node directly at the root.
before: 3 → 2 → 1 → 0 find(3) costs 3 steps
after: 3 → 0, 2 → 0, 1 → 0 find(3) costs 1 step, foreverThe chain is flattened as a side effect of asking the question. Two lines of code.
Union by rank
When merging, attach the shorter tree under the taller one. Attaching tall under short makes everything one level deeper for no reason.
rank is an upper bound on tree height — it only increases when two trees of equal rank merge.
Together these give an amortised cost so close to constant that it is treated as O(1) in practice.
Solution
def find_circle_num(is_connected: list[list[int]]) -> int:
"""Count connected components using union-find."""
n = len(is_connected)
parent = list(range(n))
rank = [0] * n
provinces = n
def find(x: int) -> int:
# Path compression: point x straight at the root.
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(a: int, b: int) -> bool:
root_a, root_b = find(a), find(b)
if root_a == root_b:
return False # already together
# Union by rank: shorter tree hangs under taller.
if rank[root_a] < rank[root_b]:
root_a, root_b = root_b, root_a
parent[root_b] = root_a
if rank[root_a] == rank[root_b]:
rank[root_a] += 1
return True
for i in range(n):
for j in range(i + 1, n): # upper triangle only
if is_connected[i][j] and union(i, j):
provinces -= 1
return provincesparent[x] = parent[parent[x]] is path halving — it flattens the chain during the walk without needing a second pass or recursion.
Complexity Analysis
Time Complexity
O(n²·α(n))
Space Complexity
O(n)
Time — the n² comes from scanning the adjacency matrix, which is unavoidable given that input format. α(n) is the inverse Ackermann function, below 5 for any input that fits in a computer — treat it as constant.
Space — two arrays of length n.
Edge Cases
Related Problems
- Redundant Connection — where union-find genuinely beats DFS
- Number of Islands — the same counting with a traversal instead
- Graphs — connectivity in general