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]

解题思路

解题思路

这是一个典型的连通分量问题，可以将城市看作图中的节点，城市间的连接关系看作边。题目要求统计有多少个连通分量（省份）。

方法一：深度优先搜索（DFS）

使用 DFS 遍历图，从每个未访问的节点开始进行深度优先搜索，每次 DFS 可以找到一个完整的连通分量。使用 visited 数组记录已访问的城市，避免重复计算。

方法二：广度优先搜索（BFS）

类似 DFS，使用队列进行层次遍历，每次 BFS 也能找到一个连通分量。

方法三：并查集（Union-Find）

通过并查集数据结构，将相连的城市合并到同一个集合中，最后统计有多少个不同的根节点即为省份数量。

推荐解法：DFS，因为实现简单，空间复杂度较低，且对于这种邻接矩阵表示的图，DFS 遍历非常直观。

算法步骤：

  1. 初始化访问数组 visited
  2. 遍历所有城市，对于未访问的城市，进行 DFS
  3. DFS 过程中标记所有相连的城市为已访问
  4. 每次 DFS 调用代表找到一个新的省份，计数器加 1

代码实现

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        vector<bool> visited(n, false);
        int provinces = 0;
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(isConnected, visited, i);
                provinces++;
            }
        }
        
        return provinces;
    }
    
private:
    void dfs(vector<vector<int>>& isConnected, vector<bool>& visited, int city) {
        visited[city] = true;
        for (int j = 0; j < isConnected.size(); j++) {
            if (isConnected[city][j] == 1 && !visited[j]) {
                dfs(isConnected, visited, j);
            }
        }
    }
};

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

public class Solution {
    public int FindCircleNum(int[][] isConnected) {
        int n = isConnected.Length;
        bool[] visited = new bool[n];
        int provinces = 0;
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                DFS(isConnected, visited, i);
                provinces++;
            }
        }
        
        return provinces;
    }
    
    private void DFS(int[][] isConnected, bool[] visited, int city) {
        visited[city] = true;
        for (int j = 0; j < isConnected.Length; j++) {
            if (isConnected[city][j] == 1 && !visited[j]) {
                DFS(isConnected, visited, j);
            }
        }
    }
}

var findCircleNum = function(isConnected) {
    const n = isConnected.length;
    const visited = new Array(n).fill(false);
    let provinces = 0;
    
    function dfs(city) {
        visited[city] = true;
        for (let i = 0; i < n; i++) {
            if (isConnected[city][i] === 1 && !visited[i]) {
                dfs(i);
            }
        }
    }
    
    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i);
            provinces++;
        }
    }
    
    return provinces;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型DFS/BFS并查集
时间复杂度O(n²)O(n²α(n))
空间复杂度O(n)O(n)

说明：

  • DFS/BFS：时间复杂度为 O(n²)，因为需要遍历整个邻接矩阵；空间复杂度为 O(n)，用于存储访问状态和递归栈空间
  • 并查集：时间复杂度为 O(n²α(n))，其中 α 是反阿克曼函数，实际上近似为常数；空间复杂度为 O(n)，用于存储父节点数组

相关题目