Module 19 · Graph Traversal and Connected Components

189. Number of Provinces

Interview · Download this solution · All solutions and shared helpers

Problem

Given a square symmetric zero/one adjacency matrix of cities, return the number of connected provinces. A one at matrix[u][v] denotes a connection. Diagonal entries do not affect component membership. Isolated cities count, and an empty matrix returns zero.

Examples

Example 1

provinces([[1,1,0],[1,1,0],[0,0,1]])
=> 2

The first two cities form one component.

Example 2

provinces([])
=> 0

There are no cities.

Example 3

provinces([[0,0],[0,0]])
=> 2

Missing diagonal self-links do not remove isolated cities.

Reveal the worked solution and reasoning

Why this mechanism works

The component protocol is unchanged from adjacency lists, but finding a city's neighbors now requires scanning its complete matrix row. This representation makes the traversal quadratic even for a graph with few edges. Mark each city before placing it on the stack.

State and boundaries

seen identifies cities assigned to a province. Each new outer-loop start creates exactly one province traversal.

Protocol

Scan city indices.
For an unseen city increment the province count and schedule it.
Pop cities and inspect every column in their row.
Schedule unseen connected cities.
Return the count.

Visualization

1 1 0
1 1 0    rows 0 and 1 belong together
0 0 1    city 2 begins a second province

Python implementation

def provinces(matrix):
    n = len(matrix)
    seen, count = set(), 0
    for start in range(n):
        if start in seen:
            continue
        count += 1
        seen.add(start)
        stack = [start]
        while stack:
            u = stack.pop()
            for v, connected in enumerate(matrix[u]):
                if connected and v not in seen:
                    seen.add(v)
                    stack.append(v)
    return count

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

provinces([[1,1,0],[1,1,0],[0,0,1]])

L2 provinces: n = len(matrix)
matrix=[[1, 1, 0], [1, 1, 0], [0, 0, 1]]; n=3

L3 provinces: seen, count = set(), 0
matrix=[[1, 1, 0], [1, 1, 0], [0, 0, 1]]; n=3; seen=set(); count=0

L4 provinces: for start in range(n):
matrix=[[1, 1, 0], [1, 1, 0], [0, 0, 1]]; n=3; seen=set(); count=0; start=0

L7 provinces: count += 1
matrix=[[1, 1, 0], [1, 1, 0], [0, 0, 1]]; n=3; seen=set(); count=1; start=0

L8 provinces: seen.add(start)
matrix=[[1, 1, 0], [1, 1, 0], [0, 0, 1]]; n=3; seen={0}; count=1; start=0

L9 provinces: stack = [start]
matrix=[[1, 1, 0], [1, 1, 0], [0, 0, 1]]; n=3; seen={0}; count=1; start=0; stack=[0]

L11 provinces: u = stack.pop()
matrix=[[1, 1, 0], [1, 1, 0], [0, 0, 1]]; n=3; seen={0}; count=1; start=0; stack=[]; u=0

L12 provinces: for v, connected in enumerate(matrix[u]):
matrix=[[1, 1, 0], [1, 1, 0], [0, 0, 1]]; n=3; seen={0}; count=1; start=0; stack=[]; u=0; v=0; connected=1

... 13 intermediate state changes omitted ...

L11 provinces: u = stack.pop()
matrix=[[1, 1, 0], [1, 1, 0], [0, 0, 1]]; n=3; seen={0, 1, 2}; count=2; start=2; stack=[]; u=2; v=2; connected=0

L12 provinces: for v, connected in enumerate(matrix[u]):
matrix=[[1, 1, 0], [1, 1, 0], [0, 0, 1]]; n=3; seen={0, 1, 2}; count=2; start=2; stack=[]; u=2; v=0; connected=0

L12 provinces: for v, connected in enumerate(matrix[u]):
matrix=[[1, 1, 0], [1, 1, 0], [0, 0, 1]]; n=3; seen={0, 1, 2}; count=2; start=2; stack=[]; u=2; v=1; connected=0

L12 provinces: for v, connected in enumerate(matrix[u]):
matrix=[[1, 1, 0], [1, 1, 0], [0, 0, 1]]; n=3; seen={0, 1, 2}; count=2; start=2; stack=[]; u=2; v=2; connected=1

Result: 2. The first two cities form one component.

provinces([])

L2 provinces: n = len(matrix)
matrix=[]; n=0

L3 provinces: seen, count = set(), 0
matrix=[]; n=0; seen=set(); count=0

Result: 0. There are no cities.

Why the solution is correct

Each inner traversal reaches exactly the cities connected to its start. Persistent visitation prevents a province from being counted again, and the outer scan eventually begins a traversal for every province. Symmetry ensures the intended undirected component interpretation.

Time and space

O(n^2) time because each visited city's full row is scanned, and O(n) auxiliary space.

Common mistakes

Counting diagonal ones counts cities, not provinces. Reporting O(V+E) without accounting for full matrix-row scans understates this implementation's cost.

Reasoning card

State: seen identifies cities assigned to a province. Each new outer-loop start creates exactly one province traversal.

Invariant: Visited cities are assigned to a counted province.

Decision to rehearse: Translate matrix relationships into DFS/BFS neighbours.

Finish: Return the count

Transfer exercise

For a large sparse graph, convert the representation to adjacency lists and compare storage and traversal costs.