Number of Provinces

LeetCode: https://leetcode.com/problems/number-of-provinces/

There are n cities. Given an n x n matrix isConnected, return the number of provinces.

1def findCircleNum(isConnected: List[List[int]]) -> int:
2    n = len(isConnected)
3    seen = set()
4    provinces = 0
5    
6    def dfs(i: int) -> None:
7        for j in range(n):
8            if isConnected[i][j] == 1 and j not in seen:
9                seen.add(j)
10                dfs(j)
11    
12    for i in range(n):
13        if i not in seen:
14            provinces += 1
15            seen.add(i)
16            dfs(i)
17    
18    return provinces

Course Schedule

provinces=1

seen=[0]

Step 1 / 4

Step 1:

Start at city 0 (unseen): provinces=1. DFS marks all cities connected to 0.

Pointers: i=0

Focus: select @ [0]

provinces=1