547. Number of Provinces

547

MediumGraph DFS and BFSDFS over an adjacency matrixConnected components count

Number of Provinces

You are given an n x n matrix isConnected where isConnected[i][j] == 1 means city i and city j are directly connected. A province is a group of cities that are directly or indirectly connected and not connected to any city outside the group. Return the total number of provinces.

Open official problem prompt ↗

In plain English

Count how many separate friend-groups (provinces) the cities fall into.

Picture it like this

Picture people at a party. You tap the first person and everyone they know, and everyone those people know, all join one huddle. When a huddle is complete you move to the next untouched person and start a new huddle. The number of huddles is the answer.

Example

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2
Why: Cities 0 and 1 are directly connected forming one province; city 2 is isolated forming a second, so there are 2 provinces.

Constraints

1 <= n <= 200n == isConnected.lengthn == isConnected[i].lengthisConnected[i][j] is 1 or 0isConnected[i][i] == 1isConnected[i][j] == isConnected[j][i]

Pattern lesson

See the pattern, then code

Connected components count

↗

Graph DFS and BFS

Connected components, grids, reachability, or unweighted shortest paths.. Each province is one connected component. Walk the graph with DFS; every time you start a new walk from an unvisited city you have discovered a fresh province, so count those launches.

New words, made simpleKnow these before the algorithm

Connected component: A maximal set of cities all reachable from one another through connections.
Adjacency matrix: isConnected[i][j] == 1 encodes an edge between city i and city j.
Visited array: Marks cities already assigned to some province so they are not recounted.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Best choiceDFS component counting

Direct and simple over the adjacency matrix.

Launch a DFS from each unvisited city, marking its whole component, and count launches.

Time O(n^2)Space O(n)

Union-Find

Also excellent, especially if edges arrive incrementally, but slightly more code here.

Union every connected pair, then count distinct roots.

Time O(n^2 * alpha(n))Space O(n)

The rule we keep true

Invariant

Every city marked visited belongs to the component of the DFS launch that first reached it, so the launch count equals the number of components.

Why this is correct

Reasoning

A DFS from a city visits exactly the cities in its connected component. Because we only start a new DFS from a city not yet visited, each component triggers exactly one launch, making the launch tally equal to the number of provinces.

The algorithm in three movesSay these aloud before coding

1Keep a visited flag per city

start c0 -> visit c0, c1 (province 1)

2Iterate over all cities

c2 unvisited -> province 2

3When you meet an unvisited city, increment the province count

count = 2

4DFS to mark every city reachable from it as visited

5Return the number of DFS launches

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

c00

c11

c22

1 · Readi=0, unvisited

2 · AskNew province?

3 · Update statecount->1, mark 0

4 · ResultDFS from 0

Key takeaway

Cities 0 and 1 merge into one province while city 2 stands alone.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-4Setup
n cities and a visited flag for each.
2
Lines 6-10DFS
From city i, visit every directly connected, unvisited city and recurse.
3
Lines 12-18Component scan
Each unvisited city begins a new province; mark it, flood its component, and bump the count.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A single city -> 1 province
No off-diagonal 1s, so every city is its own province -> n
A fully connected matrix -> 1 province
The diagonal being 1 is a self-loop and must not be miscounted

Common beginner mistakes

Counting each edge or each city instead of each component launch
Forgetting to mark the launch city visited before recursing, risking double counting
Deep recursion on a long chain can hit Python's recursion limit for large n (iterative stack avoids it)
Treating the matrix as directed even though it is symmetric

Check your understanding

How does this differ from just counting rows that contain a 1?

PyPython 3 · solution.py

Optimal

1class Solution:2    def findCircleNum(self, isConnected: List[List[int]]) -> int:3        n = len(isConnected)4        visited = [False] * n56        def dfs(i: int) -> None:7            for j in range(n):8                if isConnected[i][j] == 1 and not visited[j]:9                    visited[j] = True10                    dfs(j)1112        count = 013        for i in range(n):14            if not visited[i]:15                visited[i] = True16                dfs(i)17                count += 118        return count

Time complexityO(n^2)Optimized

Space complexityO(n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonMicrosoftBloomberg

Number of Provinces

Number of Provinces

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Graph DFS and BFS