题目描述
思路解析动画文字版
记住「从 0 往外走,遇到背离 0 的原方向边(cost=1)就计一次反转」,下面逐帧套它。
先看这张有向图:箭头就是道路的单行方向。0 号城市(绿)是大家的目的地。现在从 0 出发,沿树边往外走,逐条检查每条边的箭头是不是朝着 0。
从根 0 开始,看它直接相连的城市。
检查通往城市 1 的这条边(高亮)。看它的箭头:从 0 指向 1。
箭头从 0 指向 1,是背离 0 的方向,城市 1(及它后面的城市)没法靠这条边回到 0,必须反转。反转计数 +1 = 1。
检查通往城市 4 的这条边(高亮)。看它的箭头:从 4 指向 0。
箭头从 4 指向 0,正好朝向 0,城市 4 顺着它就能往 0 走,无需反转。计数仍是 1。
轮到城市 1:它已经能回到 0,现在看从它再往外的边。
检查通往城市 3 的这条边(高亮)。看它的箭头:从 1 指向 3。
箭头从 1 指向 3,是背离 0 的方向,城市 3(及它后面的城市)没法靠这条边回到 0,必须反转。反转计数 +1 = 2。
轮到城市 4:它已经能回到 0,现在看从它再往外的边。
检查通往城市 5 的这条边(高亮)。看它的箭头:从 4 指向 5。
箭头从 4 指向 5,是背离 0 的方向,城市 5(及它后面的城市)没法靠这条边回到 0,必须反转。反转计数 +1 = 3。
轮到城市 3:它已经能回到 0,现在看从它再往外的边。
检查通往城市 2 的这条边(高亮)。看它的箭头:从 2 指向 3。
箭头从 2 指向 3,正好朝向 0,城市 2 顺着它就能往 0 走,无需反转。计数仍是 3。
城市 5 已经接进来了,它没有更外层的新邻居,这条分支到头。
城市 2 已经接进来了,它没有更外层的新邻居,这条分支到头。
整棵树遍历完。一路上遇到 3 条「背离 0」的原方向边,它们就是必须反转的。下面把这 3 条逐一点亮。
反转边 0→1:让它改朝 0 的方向,这样城市 1 这一支就能回到 0 了。
反转边 1→3:让它改朝 0 的方向,这样城市 3 这一支就能回到 0 了。
反转边 4→5:让它改朝 0 的方向,这样城市 5 这一支就能回到 0 了。
三条边全部反转后,从任何城市出发都能开回 0 号城市。最少反转次数 = 3。回头看:整道题就是「从 0 往外走一遍,数有几条原方向背离 0 的边」。
边界:全朝向 0 是 0;全背离是 n−1;两点看那一条边。
两个追问:n−1 边且连通即树、路径唯一;cost 是把方向判断预存。
参考代码
from typing import Listclass 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复杂度
- 时间：O(n)，树有 n−1 条边,每条边在邻接表里出现两次,遍历各访问一次,共 O(n)
- 空间：O(n)，邻接表存 2(n−1) 条有向记录,加 seen / 栈,都是 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么可以保证这棵图是树、路径唯一?
追问能不能不建 cost,边遍历边判断方向?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
概率最大的路径
LeetCode 1514 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题