LeetCode 题解工作台
可以到达每一个节点的最少边反转次数
给你一个 n 个点的 简单有向图 （没有重复边的有向图），节点编号为 0 到 n - 1 。如果这些边是双向边，那么这个图形成一棵 树 。 给你一个整数 n 和一个 二维 整数数组 edges ，其中 edges[i] = [u i , v i ] 表示从节点 u i 到节点 v i 有一条 有向边…
4
题型
5
代码语言
3
相关题
当前训练重点
困难 · 图·DFS·traversal
答案摘要
时间复杂度 ，空间复杂度 。 class Solution:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·DFS·traversal 题型思路
题目描述
给你一个 n 个点的 简单有向图 （没有重复边的有向图），节点编号为 0 到 n - 1 。如果这些边是双向边，那么这个图形成一棵 树 。
给你一个整数 n 和一个 二维 整数数组 edges ，其中 edges[i] = [ui, vi] 表示从节点 ui 到节点 vi 有一条 有向边 。
边反转 指的是将一条边的方向反转，也就是说一条从节点 ui 到节点 vi 的边会变为一条从节点 vi 到节点 ui 的边。
对于范围 [0, n - 1] 中的每一个节点 i ，你的任务是分别 独立 计算 最少 需要多少次 边反转 ，从节点 i 出发经过 一系列有向边 ，可以到达所有的节点。
请你返回一个长度为 n 的整数数组 answer ，其中 answer[i]表示从节点 i 出发，可以到达所有节点的 最少边反转 次数。
示例 1：
输入：n = 4, edges = [[2,0],[2,1],[1,3]] 输出：[1,1,0,2] 解释：上图表示了与输入对应的简单有向图。 对于节点 0 ：反转 [2,0] ，从节点 0 出发可以到达所有节点。 所以 answer[0] = 1 。 对于节点 1 ：反转 [2,1] ，从节点 1 出发可以到达所有节点。 所以 answer[1] = 1 。 对于节点 2 ：不需要反转就可以从节点 2 出发到达所有节点。 所以 answer[2] = 0 。 对于节点 3 ：反转 [1,3] 和 [2,1] ，从节点 3 出发可以到达所有节点。 所以 answer[3] = 2 。
示例 2：
输入：n = 3, edges = [[1,2],[2,0]] 输出：[2,0,1] 解释：上图表示了与输入对应的简单有向图。 对于节点 0 ：反转 [2,0] 和 [1,2] ，从节点 0 出发可以到达所有节点。 所以 answer[0] = 2 。 对于节点 1 ：不需要反转就可以从节点 2 出发到达所有节点。 所以 answer[1] = 0 。 对于节点 2 ：反转 [1,2] ，从节点 2 出发可以到达所有节点。 所以 answer[2] = 1 。
提示：
2 <= n <= 105edges.length == n - 1edges[i].length == 20 <= ui == edges[i][0] < n0 <= vi == edges[i][1] < nui != vi- 输入保证如果边是双向边，可以得到一棵树。
解题思路
方法一：树形 DP
时间复杂度 ，空间复杂度 。
class Solution:
def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:
ans = [0] * n
g = [[] for _ in range(n)]
for x, y in edges:
g[x].append((y, 1))
g[y].append((x, -1))
def dfs(i: int, fa: int):
for j, k in g[i]:
if j != fa:
ans[0] += int(k < 0)
dfs(j, i)
dfs(0, -1)
def dfs2(i: int, fa: int):
for j, k in g[i]:
if j != fa:
ans[j] = ans[i] + k
dfs2(j, i)
dfs2(0, -1)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidates should demonstrate an understanding of graph traversal techniques, especially DFS and BFS.
- question_mark
Look for candidates who can break down the problem into manageable subproblems, particularly using dynamic programming on trees.
- question_mark
Watch for efficient solutions that scale well, given the problem's constraints of up to 10^5 nodes.
常见陷阱
外企场景- error
Failing to handle cases where reversing an edge is necessary for connectivity between nodes.
- error
Overcomplicating the problem by using more complex algorithms than necessary for tree-based graphs.
- error
Not considering the optimal way to track and minimize edge reversals during DFS traversal.
进阶变体
外企场景- arrow_right_alt
What if the graph were not a tree, but still had some cycles? How would this affect the approach?
- arrow_right_alt
How would the solution change if the edges could be reversed multiple times, rather than just once?
- arrow_right_alt
What happens if the graph is initially a fully connected directed graph? Can the solution be simplified?