How do I approach the Reorder Routes to Make All Paths Lead to the City Zero problem?

Start by treating the graph as undirected, then use DFS to explore from city 0. Reverse edges when encountering roads pointing away from city 0.

What is the optimal time complexity for this problem?

The optimal time complexity is O(n), where n is the number of cities. This can be achieved using DFS traversal.

How does DFS help in solving this problem?

DFS helps explore all cities and roads, ensuring we can reverse the necessary roads to make all cities accessible from city 0.

Why is this problem classified under Graph Traversal and DFS?

This problem requires traversing a graph (tree structure) and reversing edges based on direction, which is a classic DFS traversal task.

What is the space complexity of this solution?

The space complexity is O(n), which is needed for storing the adjacency list and the recursion stack during DFS.

#1466

Medium

auto_awesome图·DFS·traversal

LeetCode 题解工作台

重新规划路线

n 座城市，从 0 到 n-1 编号，其间共有 n-1 条路线。因此，要想在两座不同城市之间旅行只有唯一一条路线可供选择（路线网形成一颗树）。去年，交通运输部决定重新规划路线，以改变交通拥堵的状况。路线用 connections 表示，其中 connections[i] = [a, b] 表示从城…

深度优先搜索广度优先搜索图

题目描述

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 * 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]

lightbulb

解题思路

方法一：DFS

题目给定的路线图中有 $n$ 个节点和 $n-1$ 条边，如果我们忽略边的方向，那么这 $n$ 个节点构成了一棵树。而题目需要我们改变某些边的方向，使得每个节点都能到达节点 $0$ 。

我们不妨考虑从节点 $0$ 出发，到达其他所有节点。方向与题目描述相反，意味着我们在构建图的时候，对于有向边 $[a, b]$ ，我们应该视为有向边 $[b, a]$ 。也即是说，如果要从 $a$ 到 $b$ ，我们需要变更一次方向；如果要从 $b$ 到 $a$ ，则不需要变更方向。

接下来，我们只需要从节点 $0$ 出发，搜索其他所有节点，过程中，如果遇到需要变更方向的边，则累加一次变更方向的次数。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是题目中节点的数量。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        def dfs(a: int, fa: int) -> int:
            return sum(c + dfs(b, a) for b, c in g[a] if b != fa)

        g = [[] for _ in range(n)]
        for a, b in connections:
            g[a].append((b, 1))
            g[b].append((a, 0))
        return dfs(0, -1)

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Check for efficient DFS implementation and graph traversal logic.
question_mark
Look for correct handling of edge reversal during traversal.
question_mark
Evaluate the candidate's understanding of graph traversal patterns, especially DFS on tree structures.

warning

常见陷阱

外企场景

error
Treating the graph as directed instead of undirected during traversal.
error
Incorrectly reversing edges or failing to track reversed roads.
error
Forgetting to account for the minimum number of reversals needed.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the graph was a directed acyclic graph (DAG) instead of a tree?
arrow_right_alt
How would the problem change if there were multiple potential sources instead of just city 0?
arrow_right_alt
Consider adding additional constraints like road weight or city types. How would this affect your approach?

help

常见问题

外企场景

继续练习

#1462 课程表 IV #1377 T 秒后青蛙的位置 #1361 验证二叉树