LeetCode #547 Medium

Number of Provinces

Given an adjacency matrix of cities, count the number of connected provinces (groups of directly/indirectly connected cities).

graphdfsunion-find

Open on LeetCode ↗

02

Intuition

The trap is reading isConnected as an edge list. It is an adjacency matrix -- isConnected[i][j] == 1 means an edge, and the matrix is symmetric, so a naive loop over every pair visits each edge twice. What actually answers the question is the number of connected components: run DFS or Union-Find and count how many times a fresh traversal had to start because the city was still unvisited. Every fresh start is exactly one province, so the traversal both explores the graph and counts the answer in the same pass.

How to spot this pattern

Counting connected components: every unvisited vertex you encounter starts a new component, and one traversal claims everything reachable from it. The input is an adjacency matrix, so neighbours are found by scanning a row rather than following a list.

03

Approach

1

Read it as a matrix, not edges

isConnected[i][j] == 1 tells you cities i and j are directly connected. Because the matrix is symmetric, scanning it as if it were an edge list double counts every connection -- treat it purely as an adjacency structure to query, not a list to iterate pairwise.

2

DFS from every unvisited city

Loop i from 0 to n-1. If city i has not been visited, that means no earlier DFS reached it, so it belongs to a brand new province: increment the counter and flood-fill from i, marking every reachable city visited.

3

The counter and the traversal are the same pass

There is no separate 'count components' step. Each time the outer loop finds an unvisited city, that single event is one more province, because everything reachable from it gets marked before the loop moves on.

04

Solution & live demo

▶1class Solution:
▶2    def findCircleNum(self, isConnected):
▶3        n = len(isConnected)
▶4        visited = [False] * n
▶5        provinces = 0
▶6        def dfs(u):
▶7            visited[u] = True
▶8            for v in range(n):
▶9                if isConnected[u][v] == 1 and not visited[v]:
▶10                    dfs(v)
▶11        for i in range(n):
▶12            if not visited[i]:
▶13                provinces += 1
▶14                dfs(i)
▶15        return provinces

05

Common pitfalls

Incrementing inside the traversal

✗ Wrong

def dfs(u):
    provinces += 1
    ...

✓ Right

for i in range(n):
    if not visited[i]:
        provinces += 1
        dfs(i)

That counts vertices, not components. The increment belongs at the outer loop, where each execution marks the discovery of a region nothing before it could reach.

Marking visited after the neighbour loop

✗ Wrong

for v in ...: dfs(v)
visited[u] = True

✓ Right

visited[u] = True
for v in ...:

The matrix is symmetric, so u is its own neighbours' neighbour. Marking late means the recursion bounces back into u before the flag is set and never terminates.

Treating the matrix as an edge list

✗ Wrong

for v in isConnected[u]:

✓ Right

for v in range(n):
    if isConnected[u][v] == 1 and not visited[v]:

Iterating the row yields the 0/1 values themselves, not vertex indices, so the recursion descends into vertices 0 and 1 forever. The index is the neighbour; the value is only whether the edge exists.

06

Edge cases

All cities isolated (identity matrix off-diagonal)

Every city starts its own DFS, so provinces == n.

Fully connected matrix

First DFS visits every city; provinces == 1.

Single city

One DFS call, provinces == 1.

Matrix diagonal isConnected[i][i] == 1

Self-loops are ignored by skipping j == i during the scan; they never affect connectivity.

07

Complexity

Time

O(n^2)

Space

O(n)

Scanning the matrix dominates; the visited array and recursion stack are O(n).