LeetCode 547: Number of Provinces

Problem Restatement

We are given an n x n matrix called isConnected.

There are n cities.

If:

isConnected[i][j] == 1

then city i and city j are directly connected.

A province is a group of cities that are directly or indirectly connected to each other, with no city outside the group connected to them.

We need to return the number of provinces.

This is the same as counting connected components in an undirected graph represented by an adjacency matrix. A province may contain cities connected through intermediate cities, not only direct neighbors.

Input and Output

Item	Meaning
Input	An `n x n` matrix `isConnected`
Output	Number of provinces
Matrix value `1`	Cities are connected
Matrix value `0`	Cities are not directly connected
Graph type	Undirected graph
Goal	Count connected components

Function shape:

def findCircleNum(isConnected: list[list[int]]) -> int:
    ...

Examples

Consider:

isConnected = [
    [1, 1, 0],
    [1, 1, 0],
    [0, 0, 1],
]

City 0 is connected to city 1.

City 2 is isolated.

So there are two provinces:

{0, 1}
{2}

The answer is:

Another example:

isConnected = [
    [1, 0, 0],
    [0, 1, 0],
    [0, 0, 1],
]

No city is connected to any other city.

Each city is its own province:

{0}
{1}
{2}

The answer is:

First Thought: Treat the Matrix as a Graph

The matrix is an adjacency matrix.

Each city is a node.

Each 1 between two different cities means there is an edge between them.

So the problem becomes:

How many connected components are in this graph?

To count connected components, we can use DFS, BFS, or Union Find.

The DFS version is the most direct.

Key Insight

If we start DFS from one unvisited city, DFS will visit every city in that same province.

So each time we find an unvisited city and start a new DFS, we have discovered one new province.

The algorithm is:

number of DFS starts = number of provinces

This works because cities in the same province are all reachable from each other through direct or indirect connections.

Algorithm

Create a boolean array:

visited = [False] * n

Then scan every city.

For each city i:

If i is already visited, skip it.
If i is not visited:
1. Start DFS from i.
2. Mark every reachable city as visited.
3. Increase the province count by 1.

The DFS checks every possible neighbor j.

If:

isConnected[i][j] == 1

and city j has not been visited, then city j belongs to the same province.

Correctness

Each DFS starts from an unvisited city.

When DFS starts from city i, it follows all direct connections from i, then all direct connections from those cities, and so on. Therefore, it visits exactly the cities that are directly or indirectly connected to i.

Those cities form one province.

After this DFS finishes, every city in that province is marked visited. So none of them can start another DFS later.

If the main loop later finds another unvisited city, that city cannot belong to any previously counted province. If it did, it would have been reached and marked visited during that province’s DFS. Therefore, starting DFS from it counts a new province.

Thus, the algorithm counts every province once and only once.

Complexity

Let n be the number of cities.

Metric	Value	Why
Time	`O(n^2)`	For each city, DFS may scan a full row of the adjacency matrix
Space	`O(n)`	The visited array and recursion stack

The matrix itself is input space and is not counted as extra space.

Implementation

class Solution:
    def findCircleNum(self, isConnected: list[list[int]]) -> int:
        n = len(isConnected)
        visited = [False] * n

        def dfs(city: int) -> None:
            visited[city] = True

            for neighbor in range(n):
                if isConnected[city][neighbor] == 1 and not visited[neighbor]:
                    dfs(neighbor)

        provinces = 0

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

        return provinces

Code Explanation

We read the number of cities:

n = len(isConnected)

Then we create the visited array:

visited = [False] * n

The DFS marks the current city:

visited[city] = True

Then it scans all possible cities:

for neighbor in range(n):

If the neighbor is connected and unvisited:

if isConnected[city][neighbor] == 1 and not visited[neighbor]:

we continue DFS into that neighbor.

The main loop counts provinces:

if not visited[city]:
    provinces += 1
    dfs(city)

Each time this branch runs, we have found a new connected component.

BFS Version

DFS and BFS solve the same connectivity problem.

from collections import deque

class Solution:
    def findCircleNum(self, isConnected: list[list[int]]) -> int:
        n = len(isConnected)
        visited = [False] * n
        provinces = 0

        for start in range(n):
            if visited[start]:
                continue

            provinces += 1
            visited[start] = True
            queue = deque([start])

            while queue:
                city = queue.popleft()

                for neighbor in range(n):
                    if isConnected[city][neighbor] == 1 and not visited[neighbor]:
                        visited[neighbor] = True
                        queue.append(neighbor)

        return provinces

This version avoids recursion depth concerns.

Union Find Version

Union Find is also natural because each 1 means two cities belong to the same component.

class Solution:
    def findCircleNum(self, isConnected: list[list[int]]) -> int:
        n = len(isConnected)
        parent = list(range(n))
        rank = [0] * n

        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(a: int, b: int) -> bool:
            root_a = find(a)
            root_b = find(b)

            if root_a == root_b:
                return False

            if rank[root_a] < rank[root_b]:
                parent[root_a] = root_b
            elif rank[root_a] > rank[root_b]:
                parent[root_b] = root_a
            else:
                parent[root_b] = root_a
                rank[root_a] += 1

            return True

        provinces = n

        for i in range(n):
            for j in range(i + 1, n):
                if isConnected[i][j] == 1:
                    if union(i, j):
                        provinces -= 1

        return provinces

We start with n separate provinces.

Every successful union merges two provinces, so we subtract 1.

Testing

def run_tests():
    s = Solution()

    assert s.findCircleNum([
        [1, 1, 0],
        [1, 1, 0],
        [0, 0, 1],
    ]) == 2

    assert s.findCircleNum([
        [1, 0, 0],
        [0, 1, 0],
        [0, 0, 1],
    ]) == 3

    assert s.findCircleNum([
        [1, 1, 0],
        [1, 1, 1],
        [0, 1, 1],
    ]) == 1

    assert s.findCircleNum([
        [1],
    ]) == 1

    print("all tests passed")

run_tests()

Test	Why
Two connected cities and one isolated	Checks multiple provinces
No inter-city connections	Every city is its own province
Indirect connection	Checks transitive connectivity
Single city	Minimum input