# Number of Provinces

2 min readFeb 17, 2021

--

There are `n`

cities. Some of them are connected, while some are not. If city `a`

is connected directly with city `b`

, and city `b`

is connected directly with city `c`

, then city `a`

is connected indirectly with city `c`

.

A **province** is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an `n x n`

matrix `isConnected`

where `isConnected[i][j] = 1`

if the `ith`

city and the `jth`

city are directly connected, and `isConnected[i][j] = 0`

otherwise.

Return *the total number of *** provinces**.

**Example 1:**

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

**Output:** 2

**Example 2:**

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

**Output:** 3

分析：

DFS深度搜索，遇见一个没有见过的，mark as visited。

然后立刻DFS把他附近的也mark掉，ans+=1

Solution

`def findCircleNum(self, isConnected):`

“””

:type isConnected: List[List[int]]

:rtype: int

“””

“””

DFS the matrix, whenever we run into to a 1, run DFS and clear that island with ans + 1

“””

ans = 0

rowLen = len(isConnected)

visited = [False]*rowLen

def dfs(i):

visited[i] = True

for j in range(rowLen):

if isConnected[i][j] == 1 and not visited[j]:

dfs(j)

for i in range(rowLen):

if not visited[i]:

dfs(i)

ans += 1

return ans

iteratively可以用stack来做