有 n 個(gè)城市，其中一些彼此相連，另一些沒有相連。如果城市 a 與城市 b 直接相連，且城市 b 與城市 c 直接相連，那么城市 a 與城市 c 間接相連。
省份 是一組直接或間接相連的城市，組內(nèi)不含其他沒有相連的城市。
給你一個(gè) n x n 的矩陣 isConnected ，其中 isConnected[i][j] = 1 表示第 i 個(gè)城市和第 j 個(gè)城市直接相連，而 isConnected[i][j] = 0 表示二者不直接相連。
返回矩陣中省份的數(shù)量。

示例一.png

示例二.png

def dfs(i):
    for j in range(n):
         # 第i個(gè)城市與第j個(gè)城市相連，并且第j個(gè)城市未訪問過
        if isConnected[i][j] == 1 and visited[j] == False:
            #代表第j個(gè)城市訪問過了
            visited[j] = True
           # 找出所有與j相通的城市
            dfs(j)

n = len(isConnected)
visited = [False] * n

# 記錄省份的數(shù)量        
res = 0
# 遍歷所有的城市
for i in range(n):
    if visited[i] == False:
        dfs(i)
        res += 1
return res