个人网页制作成品下载_山西cms建站系统哪家好_百度站长工具平台_网站批量查询工具

题目

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中省份的数量。

一、代码实现

func findCircleNum(isConnected [][]int) int {n := len(isConnected)visited := make([]bool, n)count := 0for i := 0; i < n; i++ {if !visited[i] {dfs(isConnected, visited, i)count++}}return count
}func dfs(isConnected [][]int, visited []bool, i int) {visited[i] = truefor j := 0; j < len(isConnected); j++ {if isConnected[i][j] == 1 && !visited[j] {dfs(isConnected, visited, j)}}
}

二、算法分析

1. 核心思路

• 深度优先搜索(DFS)：通过DFS遍历所有相连的城市
• 访问标记：使用数组记录已访问的城市
• 省份计数：每次发现未访问的城市即表示发现一个新的省份

2. 关键步骤

1. 初始化：创建访问标记数组
2. 遍历城市：对每个未访问的城市进行DFS
3. DFS扩展：递归访问所有相连的未访问城市
4. 计数：每次DFS完成计数加1

3. 复杂度

指标	值	说明
时间复杂度	O(n²)	需要遍历整个矩阵
空间复杂度	O(n)	递归栈深度和访问数组的空间消耗

三、图解示例

四、边界条件与扩展

1. 特殊场景验证

• 单城市：返回1
• 全连通：返回1
• 全不连通：返回城市数量
• 不对称矩阵：正确处理非对称输入

2. 多语言实现

class Solution:def findCircleNum(self, isConnected: List[List[int]]) -> int:def dfs(i):visited[i] = Truefor j in range(len(isConnected)):if isConnected[i][j] == 1 and not visited[j]:dfs(j)n = len(isConnected)visited = [False] * ncount = 0for i in range(n):if not visited[i]:dfs(i)count += 1return count

class Solution {public int findCircleNum(int[][] isConnected) {int n = isConnected.length;boolean[] visited = new boolean[n];int count = 0;for (int i = 0; i < n; i++) {if (!visited[i]) {dfs(isConnected, visited, i);count++;}}return count;}private void dfs(int[][] isConnected, boolean[] visited, int i) {visited[i] = true;for (int j = 0; j < isConnected.length; j++) {if (isConnected[i][j] == 1 && !visited[j]) {dfs(isConnected, visited, j);}}}
}

五、总结与扩展

1. 核心创新点

• 图的连通分量：将问题转化为求无向图的连通分量数
• 高效遍历：利用DFS/BFS避免重复计算

2. 扩展应用

• 动态连通性：支持动态添加/删除连接
• 加权连接：考虑连接强度的省份划分
• 并行计算：对大规模城市数据使用并行DFS

3. 工程优化

• 并查集实现：使用Union-Find数据结构优化
• 迭代DFS：减少递归带来的栈空间消耗
• 内存优化：使用位图代替布尔数组