DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Number of Provinces

mediumGraphs

Problem statement

There are n cities. You get an n x n matrix isConnected where isConnected[i][j] = 1 means city i and city j are directly connected, and 0 means they are not. The matrix is symmetric and every city is connected to itself.

Connection is transitive: if a connects to b and b connects to c, all three are in the same group. A province is one such group. Return the number of provinces.

Examples

Example 1

Input: isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]

Output: 2

Explanation: Cities 0 and 3 form one province, cities 1 and 2 form the other.

Example 2

Input: isConnected = [[1, 1, 0], [1, 1, 1], [0, 1, 1]]

Output: 1

Explanation: Cities 0 and 2 are not linked directly, but both link to city 1, so all three form one province.

Hints

Approach

Depth-first search straight off the matrix. Each time you meet an unvisited city, it starts a new province; visit everything reachable from it.

  1. Keep a visited array.
  2. For each city not yet visited, add one to the count, mark it visited and push it on a stack.
  3. Pop a city, scan its row, and push every unvisited other with isConnected[city][other] == 1, marking it visited as you push.
  4. When the stack empties, that province is fully visited.

Every city is popped once and each pop scans one row of length n, giving exactly O(n^2). The input itself has n^2 cells, so nothing can do better. The explicit stack avoids recursion limits.

ComplexityTime O(n^2)Space O(n)
Python
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
stack = [start]
while stack:
city = stack.pop()
for other in range(n):
if isConnected[city][other] and not visited[other]:
visited[other] = True
stack.append(other)
return provinces

Follow-up questions

  • Return the members of each province, not just the count.
  • Links are removed over time instead of added. How would you track the province count then?

Frequently asked questions

On a full adjacency matrix both must read all n^2 cells, and DFS does it with a plain array and no extra factor. Union-find earns its place when links arrive one at a time, or when the input is an edge list too large to store as a matrix.

It is counting network partitions. Given which hosts can reach which, how many isolated groups are there? The same question appears when checking whether a cluster has split into halves that cannot see each other, or finding which subnets are joined through peering.