省份数量

标签: 深度优先搜索 广度优先搜索 并查集 图

难度: Medium

有 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]

Submission

运行时间: 27 ms

内存: 17.6 MB

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def dfs(i: int):
            for j in range(cities):
                if isConnected[i][j] == 1 and j not in visited:
                    visited.add(j)
                    dfs(j)
        
        cities = len(isConnected)
        visited = set()
        provinces = 0

        for i in range(cities):
            if i not in visited:
                dfs(i)
                provinces += 1
        
        return provinces

Explain

这个题解使用了深度优先搜索（DFS）的方法来找出省份的数量。主要思路是：从每个未访问过的城市开始，使用 DFS 遍历所有与其直接或间接相连的城市，并将其标记为已访问。每次启动一次新的 DFS 遍历，省份数量就加 1。当所有城市都被访问过后，得到的省份数量即为最终结果。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def dfs(i: int):
            for j in range(cities):
                # 如果城市 i 和城市 j 直接相连，且城市 j 未被访问过
                if isConnected[i][j] == 1 and j not in visited:
                    visited.add(j)  # 将城市 j 标记为已访问
                    dfs(j)  # 递归访问城市 j 的相连城市
        
        cities = len(isConnected)  # 获取城市数量
        visited = set()  # 记录已访问过的城市
        provinces = 0  # 记录省份数量

        for i in range(cities):
            if i not in visited:  # 如果城市 i 未被访问过
                dfs(i)  # 从城市 i 开始执行 DFS 遍历
                provinces += 1  # 省份数量加 1
        
        return provinces  # 返回最终的省份数量

Explore

在DFS遍历中，通过使用一个集合`visited`来记录已经访问过的城市，可以确保每个城市只被访问一次。在每次发现城市i和城市j直接相连时，会检查城市j是否已在`visited`集合中。如果不在，才会将其添加到`visited`中并继续进行DFS遍历。这样，即使多个城市与同一个城市直接相连，也只会在第一次遍历到该城市时将其加入到`visited`中，从而避免重复访问。

在DFS实现中，从每个未访问的城市开始新的DFS遍历是因为这样可以确保探索所有与该城市直接或间接相连的城市群，即一个省份。每次遇到未访问的城市时，意味着开始了一个新的省份的探索。除了DFS，还可以使用广度优先搜索（BFS）或并查集（Union-Find）算法来识别省份。并查集通过动态连接组件的方式，也能有效地处理省份的识别，特别是在连接关系动态变化的场景中。

在`省份数量`问题的上下文中，`isConnected`矩阵应该总是一个方阵，其中的行数和列数相等，表示城市之间的连接关系。如果`isConnected`矩阵不是方阵，即行数和列数不等，这在逻辑上是不符合题目设定的，因为每个城市应该与其他所有城市有一个明确的连接状态。如果确实遇到非方阵矩阵，算法需要进行适当的错误处理或预先验证矩阵的合法性。

在题解中，如果遇到一个完全不相连的城市，即这个城市在`isConnected`矩阵中自己与自己相连（对角线元素）外，其他元素均为0，该城市在遍历过程中会被标记为已访问。因为在进行DFS时，只有当发现某个城市与未访问的其他城市直接相连时，才会递归地继续访问其他城市。对于完全不相连的城市，DFS遍历在访问自身后将结束，因此这样的城市会被视为一个单独的省份。这也意味着每次DFS开始时，省份数量会增加1，从而正确计算包括孤立城市在内的省份数量。