重新规划路线 图解题解

这道题到底在问什么

输入

n=6, connections=[[0,1],[1,3],[2,3],[4,0],[4,5]]

输出

3(反转 0→1、1→3、4→5 这三条背离 0 的边)

输入

n=3, connections=[[1,0],[2,0]]

输出

0(两条都已朝向 0)

最优解：一步一步想明白

1. 3记住「从 0 往外走,遇到背离 0 的原方向边(cost=1)就计一次反转」,下面逐帧套它。
2. 4先看这张有向图:箭头就是道路的单行方向。0 号城市(绿)是大家的目的地。现在从 0 出发,沿树边往外走,逐条检查每条边的箭头是不是朝着 0。
3. 5从根 0 开始,看它直接相连的城市。
4. 6检查通往城市 1 的这条边(高亮)。看它的箭头:从 0 指向 1。
5. 7箭头从 0 指向 1,是背离 0 的方向,城市 1(及它后面的城市)没法靠这条边回到 0,必须反转。反转计数 +1 = 1。
6. 8检查通往城市 4 的这条边(高亮)。看它的箭头:从 4 指向 0。
7. 9箭头从 4 指向 0,正好朝向 0,城市 4 顺着它就能往 0 走,无需反转。计数仍是 1。
8. 10轮到城市 1:它已经能回到 0,现在看从它再往外的边。
9. 11检查通往城市 3 的这条边(高亮)。看它的箭头:从 1 指向 3。
10. 12箭头从 1 指向 3,是背离 0 的方向,城市 3(及它后面的城市)没法靠这条边回到 0,必须反转。反转计数 +1 = 2。
11. 13轮到城市 4:它已经能回到 0,现在看从它再往外的边。
12. 14检查通往城市 5 的这条边(高亮)。看它的箭头:从 4 指向 5。
13. 15箭头从 4 指向 5,是背离 0 的方向,城市 5(及它后面的城市)没法靠这条边回到 0,必须反转。反转计数 +1 = 3。
14. 16轮到城市 3:它已经能回到 0,现在看从它再往外的边。
15. 17检查通往城市 2 的这条边(高亮)。看它的箭头:从 2 指向 3。
16. 18箭头从 2 指向 3,正好朝向 0,城市 2 顺着它就能往 0 走,无需反转。计数仍是 3。
17. 19城市 5 已经接进来了,它没有更外层的新邻居,这条分支到头。
18. 20城市 2 已经接进来了,它没有更外层的新邻居,这条分支到头。
19. 21整棵树遍历完。一路上遇到 3 条「背离 0」的原方向边,它们就是必须反转的。下面把这 3 条逐一点亮。
20. 22反转边 0→1:让它改朝 0 的方向,这样城市 1 这一支就能回到 0 了。
21. 23反转边 1→3:让它改朝 0 的方向,这样城市 3 这一支就能回到 0 了。
22. 24反转边 4→5:让它改朝 0 的方向,这样城市 5 这一支就能回到 0 了。
23. 25三条边全部反转后,从任何城市出发都能开回 0 号城市。最少反转次数 = 3。回头看:整道题就是「从 0 往外走一遍,数有几条原方向背离 0 的边」。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        g = [[] for _ in range(n)]
        for a, b in connections:
            g[a].append((b, 1))
            g[b].append((a, 0))
        ans = 0
        stack = [(0, -1)]
        while stack:
            u, parent = stack.pop()
            for v, cost in g[u]:
                if v != parent:
                    ans += cost
                    stack.append((v, u))
        return ans

#include <vector>
using namespace std;
class Solution {
public:
    int minReorder(int n, vector<vector<int>>& connections) {
        vector<vector<pair<int,int>>> g(n);
        for (auto &e : connections) {
            g[e[0]].push_back({e[1], 1});
            g[e[1]].push_back({e[0], 0});
        }
        int ans = 0;
        vector<pair<int,int>> st{{0, -1}};
        while (!st.empty()) {
            auto [u, p] = st.back(); st.pop_back();
            for (auto [v, cost] : g[u]) if (v != p) {
                ans += cost;
                st.push_back({v, u});
            }
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int minReorder(int n, int[][] connections) {
        List<int[]>[] g = new ArrayList[n];
        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
        for (int[] e : connections) {
            g[e[0]].add(new int[]{e[1], 1});
            g[e[1]].add(new int[]{e[0], 0});
        }
        int ans = 0;
        Deque<int[]> st = new ArrayDeque<>();
        st.push(new int[]{0, -1});
        while (!st.isEmpty()) {
            int[] cur = st.pop();
            for (int[] nxt : g[cur[0]]) if (nxt[0] != cur[1]) {
                ans += nxt[1];
                st.push(new int[]{nxt[0], cur[0]});
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问