Number Of Provinces

547. 省份数量

分析

图的模型：
- 每个城市看作图中的一个节点。
- isConnected[i][j] = 1 表示城市 i 和 j 之间存在一条边
深度优先搜索（DFS）：
- 使用一个布尔数组 visited 来记录每个城市是否已访问
- 从某个未访问的城市出发，遍历与其直接或间接相连的所有城市，并标记为已访问
- 每次启动新的 DFS，意味着发现了一个新的省份
计数省份：
- 遍历所有城市，当发现一个未访问的城市时，启动一次 DFS，同时将省份数量加 1

时间复杂度

每个城市和每条边都会被访问一次，因此时间复杂度为 O(n^2)，其中 n 是城市数量

空间复杂度

访问标记数组需要 O(n) 的空间
递归栈的深度最多为 O(n)

总空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


class Solution
{
public:
    // 深度优先搜索函数
    void dfs(int city, std::vector<std::vector<int>>& isConnected, std::vector<bool>& visited)
    {
        visited[city] = true;  // 标记当前城市为已访问
        for (int neighbor = 0; neighbor < isConnected.size(); ++neighbor)
            if (isConnected[city][neighbor] == 1 && !visited[neighbor])
                dfs(neighbor, isConnected, visited);  // 递归访问相邻城市
    }

    // 主函数
    int findCircleNum(vector<vector<int>>& isConnected)
    {
        int n = isConnected.size();  // 城市数量
        std::vector<bool> visited(n, false);  // 初始化访问标记数组
        int provinces = 0;  // 省份计数

        // 遍历每个城市
        for (int i = 0; i < n; ++i)
            if (!visited[i]) // 如果城市未被访问
            {
                ++provinces;  // 新发现一个省份
                dfs(i, isConnected, visited);  // 启动深度优先搜索
            }

        return provinces;  // 返回省份数量
    }
};