Reorder Routes To Make All Paths Lead to The City Zero

1466. 重新规划路线

分析

建图：
- 将每条路线转化为一个无向图，并为每条边添加方向信息：
  - 如果路线从城市 a -> b，则图中添加边 (a, b, true)（表示这条边需要变更方向）
    - 同时添加反向边 (b, a, false)（表示这条边方向正确，无需变更）
深度优先搜索（DFS）：
- 从城市 0 开始遍历整个图，记录需要变更方向的边数：
  - 如果当前边方向不正确（change == true），则需要修改方向，计数器 res 加 1
- 继续递归访问相邻的未访问城市，确保整个图的连通性
返回结果：
- 最终 res 的值即为需要变更方向的最小路线数

时间复杂度

图中包含 n - 1 条边，DFS 遍历每条边一次，时间复杂度为 O(n)

空间复杂度

存储图的邻接表需要 O(n) 的空间
访问标记数组 visited 和递归栈的空间复杂度为 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
31
32
33
34
35
36
37
38
39
40
41
42


class Solution
{
public:
    int res = 0;  // 记录需要变更方向的路线数

    // 深度优先搜索函数
    void dfs(int city, std::vector<std::vector<std::pair<int, bool>>>& graph, std::vector<bool>& visited)
    {
        visited[city] = true;  // 标记当前城市为已访问
        for (auto t : graph[city])
        {  // 遍历所有相邻城市
            int neighbor = t.first;
            bool change = t.second;
            if (!visited[neighbor])
            {  // 如果相邻城市未访问
                if (change == true)  // 如果需要改变方向
                    ++res;
                dfs(neighbor, graph, visited);  // 递归访问相邻城市
            }
        }
    }

    // 主函数
    int minReorder(int n, vector<vector<int>>& connections)
    {
        // 构建图
        std::vector<std::vector<std::pair<int, bool>>> graph(n);
        for (auto conn : connections)
        {
            graph[conn[0]].push_back({conn[1], true});  // 原方向
            graph[conn[1]].push_back({conn[0], false}); // 反方向
        }

        // 初始化访问标记数组
        std::vector<bool> visited(n, false);

        // 从城市 0 开始深度优先搜索
        dfs(0, graph, visited);

        return res;  // 返回需要变更方向的最小数目
    }
};