LC 1466. 重新规划路线

题目描述

这是 LeetCode 上的 1466. 重新规划路线 ，难度为 中等。

n 座城市，从 0 到 n-1 编号，其间共有 n-1 条路线。

因此，要想在两座不同城市之间旅行只有唯一一条路线可供选择（路线网形成一颗树）。

去年，交通运输部决定重新规划路线，以改变交通拥堵的状况。

路线用 connections 表示，其中 $connections[i] = [a, b]$ 表示从城市 a 到 b 的一条有向路线。

今年，城市 0 将会举办一场大型比赛，很多游客都想前往城市 0 。

请你帮助重新规划路线方向，使每个城市都可以访问城市 0。返回需要变更方向的最小路线数。

题目数据保证每个城市在重新规划路线方向后都能到达城市 0 。

示例 1：

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

输出：3

解释：更改以红色显示的路线的方向，使每个城市都可以到达城市 0 。

示例 2：

输入：n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]

输出：2

解释：更改以红色显示的路线的方向，使每个城市都可以到达城市 0 。

示例 3：

输入：n = 3, connections = [[1,0],[2,0]]

输出：0

提示：

• $2 <= n <= 5 \times 10^4$
• $connections.length = n-1$
• $connections[i].length = 2$
• $0 <= connections[i][0], connections[i][1] <= n-1$
• $connections[i][0]$ != $connections[i][1]$

---

DFS

核心等价：原图上从所有点能够访问到 0，等价于反图中从 0 出发能到任何点。

因此，可用 connections 创建双向图（原边权重为 $1$，反向边权重为 $0$），然后从 0 出发访问整张图，统计访问过程中的权重之和，即是原图中需要反向的边的数量。

Java 代码：

class Solution {
    int N = 50010, M = N * 2, idx = 0;
    int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    void add(int a, int b, int c) {
        e[idx] = b;
        ne[idx] = he[a];
        w[idx] = c;
        he[a] = idx++;
    }
    public int minReorder(int n, int[][] connections) {
        Arrays.fill(he, -1);
        for (int[] info : connections) {
            int a = info[0], b = info[1];
            add(a, b, 1); add(b, a, 0);
        }
        return dfs(0, -1);
    }
    int dfs(int u, int fa) {
        int ans = 0;
        for (int i = he[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (j == fa) continue;
            ans += w[i] + dfs(j, u);
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    int N = 50010, M = N * 2, idx = 0;
    int he[50010], e[100020], ne[100020], w[100020];
    void add(int a, int b, int c) {
        e[idx] = b;
        ne[idx] = he[a];
        w[idx] = c;
        he[a] = idx++;
    }
    int minReorder(int n, vector<vector<int>>& connections) {
        memset(he, -1, sizeof(he));
        for (auto& info : connections) {
            int a = info[0], b = info[1];
            add(a, b, 1); add(b, a, 0);
        }
        return dfs(0, -1);
    }
    int dfs(int u, int fa) {
        int ans = 0;
        for (int i = he[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (j == fa) continue;
            ans += w[i] + dfs(j, u);
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        N, M, idx = n + 10, (n + 10) * 2, 0
        he, e, ne, w = [-1] * N, [0] * M, [0] * M, [0] * M

        def add(a, b, c):
            nonlocal idx
            e[idx], ne[idx], w[idx], he[a] = b, he[a], c, idx
            idx += 1

        def dfs(u, fa):
            ans = 0
            i = he[u]
            while i != -1:
                j, c = e[i], w[i]
                i = ne[i]
                if j == fa: continue    
                ans += c + dfs(j, u)
            return ans

        for a, b in connections:
            add(a, b, 1)
            add(b, a, 0)
        return dfs(0, -1)

TypeScript 代码：

function minReorder(n: number, connections: number[][]): number {
    let N = n + 10, M = N * 2, idx = 0;
    const he = Array(N).fill(-1), e = Array(M).fill(0), ne = Array(M).fill(0), w = Array(M).fill(0);
    const add = function(a: number, b: number, c: number): void {
        e[idx] = b;
        ne[idx] = he[a];
        w[idx] = c;
        he[a] = idx++;
    };
    const dfs = function(u: number, fa: number): number {
        let ans = 0;
        for (let i = he[u]; i != -1; i = ne[i]) {
            const j = e[i];
            if (j == fa) continue;
            ans += w[i] + dfs(j, u);
        }
        return ans;
    };
    for (let [a, b] of connections) {
        add(a, b, 1); add(b, a, 0);
    }
    return dfs(0, -1);
};

• 时间复杂度：建图复杂度为 $O(n)$；从 0 点开始遍历，访问所有点并统计权重之和的复杂度为 $O(n)$。整体复杂度为 $O(n)$
• 空间复杂度：$O(n)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1466 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。