1466. Reorder Routes to Make All Paths Lead to the City Zero¶
题目信息¶
- 题号:
1466
- 难度:
Medium
- 主题:
树、图遍历、边方向
- 原题:
- 重点:
忽略方向后道路构成一棵树;反转最少道路,使每个城市都能沿有向路径到达城市
0
题目重述¶
有 n 个城市和 n-1 条单向道路,connections[i] = [a,b] 表示道路从 a 指向 b。忽略方向后,所有城市连通且不存在环。
可以反转任意道路方向。请返回最少反转次数,使每个城市都能沿道路方向到达城市 0。
2 <= n <= 5 * 10^4,城市编号合法,输入无重复道路。
自建示例¶
只需反转离开城市零的道路:
输入:n = 3, connections = [[0,1],[2,1]]
输出:1
解释:把 0 -> 1 反转为 1 -> 0 后,城市 2 可沿 2 -> 1 -> 0 到达城市 0。
所有道路已经朝向城市零时无需反转:
输入:n = 3, connections = [[1,0],[2,1]]
输出:0
解释:每个城市原本就存在通往城市 0 的有向路径。