Number of Provinces

Medium#547

There are n cities and a square matrix isConnected: isConnected[i][j] is 1 when cities i and j are directly connected and 0 when they are not. A province is a group of cities that reach each other directly or through other cities. Count the provinces. Our example: [1, 1, 1, 0, 0], [1, 1, 1, 0, 0], [1, 1, 1, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 1, 1] → 2.

547 Number of ProvincesWalkthrough · 1×

Example: [1, 1, 1, 0, 0], [1, 1, 1, 0, 0], [1, 1, 1, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 1, 1]: pairs 0–1, 0–2, 1–2 and 3–4. The third pair joins nothing new: 1 and 2 already share the root 0.

01234011100111100211100300011400011isConnected012340011223344parent
looking at nowroot of a provincea 1 already usedon or below the diagonal: skipped

Each city is its own root

01/53
restart · back · play · step
Speed
1function findCircleNum(isConnected):
2 parent = [0, 1, ..., n - 1]
3 provinces = n
4 for each pair i < j with isConnected[i][j] == 1:
5 rootI = find(i)
6 rootJ = find(j)
7 if rootI is not rootJ:
8 parent[rootJ] = rootI
9 provinces = provinces - 1
10 return provinces
11
12function find(x):
13 while parent[x] is not x:
14 x = parent[x]
15 return x
state
parent
[0, 1, 2, 3, 4]
provinces
–
i
–
j
–
rootI
–
rootJ
–
x
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Every city starts as a province of its own, and a direct link merges the two provinces it touches, so in the end a province holds exactly the cities that reach each other.
  2. The count drops only when the two roots differ. A link inside one province, like 1–2 here, changes nothing, so cities are never counted twice.
  3. The matrix is symmetric and its diagonal says only that a city is linked to itself, so the 1s above the diagonal are enough.

Complexity

Time O(n² · h): all pairs of the matrix are looked at, and each 1 costs two finds as deep as the trees, which is up to n here and almost a constant with re-hanging on the root and the smaller tree under the bigger. Memory O(n) for parent.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.