547. 省份数量 · Algorithm Lab

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。返回矩阵中省份的数量。

示例 1：

输入： isConnected = [[1,1,0],1,1,0,0,0,1] 输出： 2

示例 2：

输入： isConnected = [[1,0,0],0,1,0,0,0,1] 输出： 3

提示：

1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] 为 1 或 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]

参考解法

下面保留的是原始练习仓库中的个人作答，可在右侧工作台中独立重写，再按需揭示对照。

python


class Solution(object):
    def findCircleNum(self, isConnected):
        n = len(isConnected)
        visited = [False] * n
        province_count = 0

        def dfs(current):  # 遍历和current连通的所有城市
            visited[current] = True
            for j in range(n):
                if isConnected[current][j] == 1 and not visited[j]:
                    dfs(j)
        
        for i in range(n):  # 遍历所有城市
            if not visited[i]:
                province_count += 1
                dfs(i)

        return province_count
        """
        :type isConnected: List[List[int]]
        :rtype: int
        """