企业官网建设流程全解析

今天想聊聊一道经典得不能再经典的图论题：编号802的“找到最终的安全状态”。只要看到副标题写着“拓扑排序”，大概就能猜到解法不在于暴力模拟每条路径，而在于沿着图的结构做一次反方向的剥离。题目本身不复杂：给一张有向图，找出所有“安全节点”。但“安全”这两个字在不同表述里有点绕，很多第一次接触的朋友会卡在读题上，而不是卡在写代码上。

这道题适合三类人：刚接触拓扑排序的初学者、刷题想搞懂反向建图逻辑的开发者、以及准备面试需要快速复盘图论套路的求职者。我下面把从读题、建图、跑BFS到踩坑调试的完整思路记录下来。先把结论放在前面：安全节点和“能从环外一直走出去”的节点是同一批，而拓扑排序恰好能把它们逐层筛出来。理解了这一点，整道题就是几十行代码的事。

1. 题目到底在说什么：安全状态要先翻译成人话

1.1 “所有路径最终到达终端节点”到底是什么意思

有向图的每个节点都有一个或多个出边，也可能没有出边。出度为 0 的节点叫终端节点，走到这里就停住了。题目要求的是：从某个节点出发，不管你怎么沿着出边走，只要所有可能路径最后都会停在某个终端节点上，那这个节点就是“安全节点”。

这跟现实里判断一个人能不能“平安落地”很像：把每次选择一条出边看成一次决策，如果无论怎么选都只在有限步内结束，不会陷入无限转圈，你才叫安全；只要存在一条路能让你永远绕圈子，你就不安全。这里的“永远绕圈子”对应到图上就是一个环，可能是自己指向自己的自环，也可能是好几个节点连成的有向环。

1.2 先想清楚：哪些节点一定不安全

顺着这个比喻，不安全的节点有两类：第一类自身在一个有向环里；第二类不在环里，但存在一条路径能走进某个有向环。第二类很容易被忽略。举个例子，A 走向 B，B 走向 C，C 又指向 B，那么 A 也是不安全的，因为它确实有一条路径会在 B、C 之间无限循环。题目里“所有路径”这个限定词非常关键，它把答案从“存在一条好路”提升成了“没有任何坏路”。掉进这个坑的人，往往会用 DFS 找一条到终端节点的路径就判定安全，这样一定会错。

所以，问题的本质可以改写成一个更干净的判定：安全节点 = 不位于任何环上，并且无法到达任何环的节点。这个改写是整道题建模的起点。反过来说，如果一个节点所能到达的所有节点都是安全的，那它自己当然也是安全的；如果它能到达某个不安全节点，那它也不安全。后面所有算法，本质上都是在维护这个集合。

2. 为什么能想到拓扑排序：两件事想通就豁然开朗

2.1 先忘掉拓扑排序，想一种朴素的“剥洋葱”

假设你已经知道了哪些节点是终端节点。终端节点一定安全，因为从它出发没有路径可走，所有路径（空集）当然都停在终端节点。那接下来呢？如果一个节点的所有出边都指向已经确定安全的节点，那它自己也安全，因为无论走到哪个下一跳，最终都会安全。这个过程可以一直向前扩散：安全集合会从终端节点一点点向图的上游蔓延。典型的一层一层向外剥，跟剥洋葱一模一样。

反过来想更漂亮。每次确定一批新的安全节点后，剩下的图中，那些原本出度为 0 的节点会被“剥掉”；剥掉之后，某些节点的出度会变成 0，它们又成为新的安全节点。于是整个问题就变成了：反复删除出度为 0 的节点，把所有能被删掉的节点收集起来。如果某个节点在环上，它的出度永远无法被削成 0，因为环上的每个点都至少有一条指向环内节点的边，除非整条环都被消掉，否则它不可能变成“没有出边”的状态。

2.2 为什么需要反向建图

标准的 Kahn 拓扑排序是以“入度为 0”为入口开始删点的。但我们这里要反复删的是“出度为 0”的点，直接套标准模板不太顺手。解决办法非常朴素：把每条边方向反过来。原来 u -> v，改成 v -> u。这样原图中的出度就变成了反图中的入度，原图中出度为 0 的终端节点，正好就是反图中入度为 0 的起点。于是“反复删出度为 0 的点”完美翻译成“反复删反图中入度为 0 的点”，这就是一套标准 Kahn 模板能跑的东西。

这个“反图 + 入度”的组合是本题最大的思维跳跃。很多代码你一看就懂，但自己想不出来，差的就是这一步：原问题的方向是从一个节点往外走，判断它能不能到达终点；拓扑排序的方向却是从终点往回找哪些节点能到达终点。既然方向相反，那就反着建图。这个思路一旦转过来，后面就是机械执行了。

3. 完整实操：邻接表、出度数组、BFS 三步走

3.1 构造反图和出度数组

算法步骤如下。第一步，遍历原始 graph。因为输入通常直接给了邻接表，graph[u] 是 u 的所有出边列表，所以只用一遍循环就能同时得到两个东西：outDegree[u] 记录 u 的出边总数；revGraph[v] 里塞入 u，代表反向边 v -> u。

class Solution { public: vector<int> eventualSafeNodes(vector<vector<int>>& graph) { int n = graph.size(); vector<vector<int>> revGraph(n); vector<int> outDegree(n, 0); for (int u = 0; u < n; ++u) { for (int v : graph[u]) { revGraph[v].push_back(u); ++outDegree[u]; } } } };

这里有个细节值得多说一句：不要边遍历边把 outDegree 建好后直接进入 BFS，而是先把队列初始化也放在同一遍循环之外。我见过有人把终端的判断放在循环里顺手入队，代码也能跑，但可读性差。按“先建图、后初始化队列、再 BFS”的三段式写，结构最清晰，也方便遇到问题时逐步调试。建反图时注意，revGraph 的索引是原图中的目标节点，批量往里面塞的是原图中的来源节点，这个方向别搞反，否则 BFS 时你遍历到的“前驱”就全错了。

3.2 BFS 的核心逻辑：谁脱颖而出

第二步，初始化队列。把所有 outDegree[u] == 0 的节点入队，这些就是终端节点。第三步，循环弹出节点 v，标记 safe[v] = true，然后遍历 revGraph[v] 里的所有前驱 u。u 原本有一条 u -> v 的出边，现在 v 被删掉了，所以 u 的出度要减一；当 u 的出度变成 0，说明 u 指向的节点全都被确认安全了，u 自己也安全，入队。

queue<int> q; vector<bool> safe(n, false); for (int i = 0; i < n; ++i) { if (outDegree[i] == 0) { q.push(i); } } while (!q.empty()) { int v = q.front(); q.pop(); safe[v] = true; for (int u : revGraph[v]) { --outDegree[u]; if (outDegree[u] == 0) { q.push(u); } } } vector<int> result; for (int i = 0; i < n; ++i) { if (safe[i]) { result.push_back(i); } } return result; }

最后一步收集答案时，直接按编号从小到大扫描 safe 数组，天然就是升序。这里要注意，不能把 BFS 出队的顺序直接当答案，因为队列顺序取决于入队时机，和节点编号没有关系，必须最后统一扫一遍。

3.3 用手推一个小图，把整个过程走一遍

构造一个 5 个节点的例子：0 -> 1，0 -> 2，1 -> 2，3 -> 1，3 -> 4，4 -> 4。节点 2 是终端节点，出度为 0；节点 4 是自环，不可能安全。初始 outDegree 分别是 0:2、1:1、2:0、3:2、4:1，队列初始只有 2。弹出 2 后，反向图中 rev[2] 里有 0 和 1，它们各少一条出边：0 剩下指向 1 的边，1 出度变成 0，于是 1 入队。弹出 1 后，rev[1] 里有 0 和 3，0 的出度变成 0，入队；3 的出度从 2 变成 1。弹出 0，rev[0] 里没有别的节点。最终 safe 集合是 {0,1,2}，3 因为还有一条到 4 的出路，出度始终为 1，永远不能入队，正确判定为不安全。

这个例子还反映了一个很关键的直觉：安全集合不是从图中间蹦出来的，而是从终点反向推进，谁“与终点之间的路径全是单向且无环的”，谁才会被包括进来。

3.4 时间与空间复杂度

每条边在构建反图时访问一次，在 BFS 里又会因为反向边被访问一次，所以时间复杂度是 O(N + M)。空间上，反图、出度数组、队列、safe 数组一起是 O(N + M) 量级。题目规模较大时，O(N + M) 已经是最优级别，不需要也不可能更快。这里补一句：输入如果是邻接矩阵而不是邻接表，建图成本会变成 O(N^2)；好在本题输入按邻接表给出，所以我们直接复用即可，这也是为什么算法的核心复杂度能保持线性。

4. 代码细节与常见雷区：这些坑我几乎每次都会看到

4.1 只认“一条路能到达终点”会全盘皆输

这是最大的坑。题目明确说“从该节点出发的所有路径”，不是存在一条。有人第一反应写一个 DFS(u)，只要有某条路径能到终端节点就返回 true，然后把 u 标记为安全。这种解法在小图里能过，遇到下面这张图就会错：0 -> 1，1 -> 2，2 -> 1，同时 0 -> 3，3 是终端节点。节点 0 虽然能走到安全的 3，但也存在 0 -> 1 -> 2 -> 1 的环上路径，所以 0 不安全。只找一条出路的人会错误地返回 0。解决这个问题的正路是全局视角：不应站在单个节点上找路，而应当从终端节点反向做集合扩散。

4.2 自环和多重边的边界问题

自环的特殊性在于它永远不会变成“出度为 0”：如果节点 u 有自环，在反向图里它也有 u -> u 的边，在 BFS 中它自己的出度会包含一条指向自己的边，除非整张图被清空，否则不可能归零。所以自环节点不会被标记为安全，这符合定义。我在本地测试时特意构造了单节点自环的用例，输入是[[1]]，期望结果是空数组，代码直接返回空，符合预期；如果习惯性认为“只有一个节点，没有别的路径，所以安全”，那就踩坑了。

多重边也不需要刻意去重。每条 u -> v 都会给 outDegree[u] 加 1，反向图会有重复的 v -> u。当 v 被删除时，需要循环两次才能把 u 的出度消掉两次，最终效果一致。如果误用了去重，出度会算错，反而可能导致环内节点被误判成安全。所以千万不要自作主张加个 set 去重，让它原样计数才是对的。

4.3 为什么直接按删除顺序输出答案会不对

给一个反例：节点编号 0 在最后一步才被剥出来，编号 1 却在第一步就入队了。如果按 BFS 出队顺序收集，答案可能是 {1,0} 或者更乱；题目要求升序返回。所以标准写法是最后再扫一遍 safe 数组。只要 safe 数组标记正确，顺序就是确定且合法的。这个“最后统一收集”的习惯在拓扑排序类题目里很通用，因为 BFS 出的顺序往往依赖图的形态，跟编号无关。

还有一个隐藏细节：在循环中修改 outDegree，可以理解为“剩余图中该节点还没有被删掉的出边数”。很多图论教材在 Kahn 算法里也是这么复用入度数组的，所以这个数组在 BFS 结束后值不再有意义，不要拿它去判断节点安全与否。如果调试时看到 outDegree 变化很大，别慌，那说明图被剥得很快，恰恰是正确信号。

4.4 不同语言的实现差异

C++ 里 vector<vector > 传引用即可，不需要拷贝。Python 里用 collections.deque 做队列，不要用 list 当队首 pop(0)，那样会退化成 O(N^2)。Python 版本可以这样写：

from collections import deque def eventualSafeNodes(graph): n = len(graph) rev_graph = [[] for _ in range(n)] out_degree = [0] * n for u, neighbors in enumerate(graph): for v in neighbors: rev_graph[v].append(u) out_degree[u] += 1 q = deque(i for i in range(n) if out_degree[i] == 0) safe = [False] * n while q: v = q.popleft() safe[v] = True for u in rev_graph[v]: out_degree[u] -= 1 if out_degree[u] == 0: q.append(u) return [i for i in range(n) if safe[i]]

两种语言逻辑完全一致，只要把队列和建图写对，跑出来的结果就是同一份。

5. 另一种同样主流的解法：DFS 三色标记法

5.1 三色标记在干什么

除了拓扑排序，这道题的另一个广为人知解法是 DFS 加三色标记。三色指：0 表示还没访问，1 表示正在当前 DFS 栈中，2 表示已经处理完且确认安全。对每个节点做 DFS，遍历它的所有邻居；如果遇到颜色 1 的节点，说明当前路径出现环，整个递归链不安全；如果所有邻居的颜色都是 2，当前节点就可以标记为 2。

def eventualSafeNodes(graph): n = len(graph) color = [0] * n def dfs(u): if color[u] > 0: return color[u] == 2 color[u] = 1 for v in graph[u]: if not dfs(v): return False color[u] = 2 return True return [u for u in range(n) if dfs(u)]

这里的核心是“递归中途遇到灰色节点即可返回 False”，因为在有向图中，遇到灰色意味着当前深度优先探索的路径绕回了自己，一定存在环。这种写法不需要建反图，空间上比拓扑排序版本更省一点，因为直接复用原邻接表。

5.2 拓扑排序和三色标记怎么选

两种解法的时间复杂度都是 O(N + M)，空间也都在 O(N) 附近。实际面试或笔试中，我更建议优先写三色标记，因为代码量小、含义直观，不太容易建错图。但如果是想展示建模能力，或者在讨论环节要解释“为什么反向建图”，拓扑排序版本更优雅，它能引导出“安全节点是可从终端节点反向剥出来的集合”这个本质。

下面用一个表格对比：

从刷题角度，我的建议是两种都要会写。拓扑排序版能帮忙理解这一类“反向剥皮”的题，三色标记版则是考场上兜底的手速解法。

6. 这道题背后真正值得带走的两个套路

6.1 “从出口反向删除”能解决什么问题

很多有向图上“判断哪些节点能安全终止”的问题，本质都能用反向删除解决。比如有的题目问“哪些节点最终不会陷入循环”，有的问“哪些节点在所有路径上都能到达某些特殊节点”，这些都可以尝试把特殊节点作为初始队列，反向建图后跑同样的 BFS。判断的标准只有一个：如果一个节点的所有出边都指向已确认节点，那它也能被确认；这个过程循环往复，直到队列为空。

我平时遇到这类题，第一反应不是马上 DFS，而是先问自己：能不能把问题反转过来，把“每个节点需要满足所有后继”变成“从特殊集合向源头扩散”？能反转，多半就是拓扑排序；不能反转，再考虑 DFS 状态机。这个问法帮我解决过不少看起来毫无头绪的图论题。

6.2 遇到图论题时的快速判断模板

拿到一道有向图题，先按下面三步走：第一步看结果是不是一组节点；第二步看判定条件是不是跟“环”或“所有路径”相关；第三步看能不能从边界出发反向扩散。三步都满足，基本就是 802 的变种。如果题目还要输出顺序，那就在反向删除的基础上额外记录步数或顺序；如果题目只要判断单个节点，三色标记通常更直接。

我曾经用随机生成的大图做压力测试，把拓扑排序结果和三色标记结果逐节点对比，验证两者集合完全一致。有个很反直觉的发现：在图上看起来离环很远的节点，只要存在一条到环的路径，就一定会被排除；拓扑排序不会因为“它在环上的概率低”就网开一面。这也是这类题最迷人的地方——判定条件是严格的全称量词，差一条边都不行。

这题我前前后后写过不下三遍，每次隔一段时间重做都有新体会。第一次写，我卡在“所有路径”上，写了个只找一条出路的 DFS；第二次卡在反向建图上，想不通为什么拓扑排序能找“安全”，后来在纸上画了两个小时的剥洋葱过程才明白；第三次才把两种解法都写熟。个人最大的建议是：不要只背代码，拿一个带环的图画一遍删除过程，比看十篇题解都管用。最后分享一个小技巧，这道题如果改成“判断单点是否安全”，拓扑排序依然可以先预处理出 safe 数组，查询时 O(1) 返回；如果题目要求多次查询，这个预处理结构可以让总复杂度保持在线性级别。希望这篇复盘能帮你把“反图 + 拓扑排序”变成自己的肌肉记忆。