省份数量

难度: 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]

注意：本题与主站 547 题相同： https://leetcode-cn.com/problems/number-of-provinces/

Submission

运行时间: 28 ms

内存: 16.9 MB

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        ans = 0
        n = len(isConnected)
        visited = [0] * n

        def dfs(index):
            for j in range(len(isConnected)):
                if isConnected[index][j] and visited[j] == 0:
                    visited[j] = 1
                    dfs(j)

        for i in range(n):
            if visited[i]==0:
                dfs(i)
                ans += 1

        return ans

Explain

此题解使用了深度优先搜索（DFS）来确定省份数量。矩阵 `isConnected` 表示城市间的连接状态。我们维护一个 `visited` 数组来记录已经访问过的城市。对于每个城市，如果它还没有被访问过，就从这个城市开始进行深度优先搜索，并将搜索到的所有城市标记为已访问。这样可以确保通过间接连接也能访问到的所有城市都被遍历一次，形成一个省份。每次从未访问的城市开始新的DFS都表示发现了一个新的省份，因此每次启动DFS后，省份计数增加。

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

空间复杂度: O(n)

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        ans = 0  # 初始化省份数量为0
        n = len(isConnected)  # 城市的数量
        visited = [0] * n  # 访问状态数组

        def dfs(index):
            for j in range(len(isConnected)):
                # 如果城市j与当前城市index连接且未被访问过
                if isConnected[index][j] and visited[j] == 0:
                    visited[j] = 1  # 标记城市j为已访问
                    dfs(j)  # 递归访问城市j

        for i in range(n):
            if visited[i] == 0:  # 如果城市i未被访问过
                dfs(i)  # 从城市i开始DFS
                ans += 1  # 完成一次DFS后，省份数量增加

        return ans

Explore

在深度优先搜索中确实存在递归栈溢出的风险，尤其是当数据规模很大时。为了防止这种情况，可以采取以下措施：1. 优化递归深度，例如通过减少不必要的递归调用。2. 在可能的情况下使用迭代版本的DFS，利用显式栈来管理状态而非依赖系统调用栈。3. 在某些编程环境中，可以考虑增加系统栈的大小限制。4. 对于特别大的数据集，考虑使用非递归的图遍历方法，如广度优先搜索（BFS）。

题目中的矩阵 `isConnected` 通常是一个正方形矩阵，因为它表示的是城市之间的连接状态，其中矩阵的行和列都代表同样的城市集合。如果不是正方形矩阵，则可能表示输入数据有误或问题描述不正确，因为在城市间的连接矩阵中，行和列的数量不等将无法正确表示城市间的相互关系。在实际应用中，如果遇到这种情况，应首先验证输入数据的有效性并修正或报错。

在DFS中，矩阵的对角线元素（即城市自己与自己的连接）通常应当设为1，表示每个城市至少与自己是连通的。这种设置不影响省份的计数，因为DFS搜索时是基于城市间是否有直接或间接的连接进行的，对角线元素为1仅确认了城市自连的基本事实，不会导致额外的省份计数。在DFS的实现中，通常也不会单独对一个城市进行访问，而是查看与其他城市的连接状态。