企业官网建设流程全解析

第一次刷到 802 题“找到最终的安全状态”时，我盯着题目名看了半天：安全状态是什么状态？等把图论背景补上之后才发现，这题实际上是在问一件很简单的事——在一个有向图里，找出所有“从它出发，无论沿着哪条边走，最终都会停在某个终端节点”的节点。翻译成人话就是，这些节点永远不会走进环里，也不会走到通向环的路径上。解法里最经典的套路是拓扑排序，更准确地说，是反向建图之后做的一轮出度归零 BFS。这篇文章打算把这道题讲透：题目怎么理解、为什么拓扑排序能解、代码怎么写、有哪些坑、以及这个思路在真实工程里还能用在什么地方。适合正在刷图论题的人、准备算法面试的人，以及所有想真正搞懂拓扑排序本质的读者。

1. 做题前先搞懂：“安全状态”到底在说什么

1.1 终端节点和安全节点是两个锚点

题目里有两个关键定义，一个是终端节点，一个是安全节点。终端节点指没有出边的节点，也就是出度为 0 的节点，它没有后续，路径走到这里就算结束。安全节点则是指从它开始的所有路径，最终都能到达某个终端节点。注意这里说的是“所有路径”，不是“存在一条路径”，这一点特别容易看漏。

我举个例子。假设有 6 个节点，编号 0 到 5，边是这样：

• 0 -> 1
• 1 -> 2
• 2 没有出边
• 3 -> 1
• 4 -> 3
• 5 -> 5（自环）

直观上看，0、1、2、3、4 这些节点无论怎么走，最后都会停在 2 这个终端节点上，所以它们都是安全节点。而 5 指向自己，它会一直绕着自环转，永远停不下来，不安全。如果我把边 4 -> 3 改成 4 -> 5，那 4 也不安全了，因为从 4 出发有一条路径会走进 5 的自环。这个改动正好说明一个关键性质：一个节点是否安全，完全取决于它的后继节点是否安全，这是整道题最核心的递推关系。

1.2 不在环上不等于安全

很多初学者会把这道题理解成“找出所有不在环上的节点”，这个直觉只对了一半。自己不在环上，不代表它不会走到环里去。

比如一个简单的例子：3 个节点，0 -> 1，1 -> 2，2 -> 1。这里 1 和 2 构成一个环，0 并不在环里，但 0 有一条路径能走到这个环，所以在 0 出发的路径中，存在一条永远不会停在终端节点的路径，0 就不安全。反过来想，安全节点的条件比“不在环上”更严格：它必须对环有绝对的绝缘，所有路径的终点都得是终端节点。

这个理解直接决定了算法设计。如果你一上来就去求“哪些节点不在任意一个环中”，然后用补集的方式得到答案，大概率会在指向环的那类节点上翻车。正确的模型应该是：安全集合是一个从终端节点出发、沿着反向边不断扩散的集合。

2. 拓扑排序为什么恰好能解这道题

2.1 两个关键观察

要理解拓扑排序为什么是这道题的正解，先看两个朴素观察。

第一个观察：终端节点一定是安全节点。因为它没有出边，路径走到这里就结束了，没有继续走下去的可能，自然满足“所有路径最终到达终端节点”的定义。

第二个观察：如果一个节点的所有后继节点都是安全节点，那它本身也是安全节点。因为从它出发，第一跳到达的任意节点都已经保证最终能走到终端节点，剩下的路径和被到达的安全节点完全一样，所以它同样安全。

这两个观察合在一起，就是一个递归定义：安全节点要么是终端节点，要么所有边都指向安全节点。顺着这个定义往下挖，你会发现它其实和“剥洋葱”很像——先把最外层没有出边的终端节点拿掉，然后露出新的一层，判断这一层是否所有边都指向已经被拿掉的部分，如果是，就继续拿掉。这正是一轮从终点往回推的过程，也就是反向拓扑排序。

2.2 反向建图加出度归零：完整的算法流程

既然递推方向是从后继到前驱，那直接顺着原图遍历就吃亏了，我们需要一个反向图来快速找到“谁指向当前节点”。完整步骤如下：

1. 建立反向图 rev：如果原图存在 u -> v，就在 rev[v] 中加入 u。
2. 统计每个节点在原图中的出度 out_degree[u]。
3. 把所有出度为 0 的节点放入队列，并标记为安全。
4. 弹出队首节点 cur，遍历 rev[cur] 中的所有前驱节点 pre。因为 cur 已经被确认安全，相当于 pre 原本指向 cur 的那条边已经“消失”，所以 out_degree[pre] 减 1。
5. 如果 out_degree[pre] 减到 0，说明 pre 的所有后继节点都已经确认安全，那 pre 也安全，入队并标记。
6. 队列清空后，所有标记为安全的节点就是答案，按编号升序输出即可。

这个过程里最关键的点是第 4 步和第 5 步：我们不是真的去删除图里的边，而是通过维护“还剩几条出边”的计数器来模拟删除。每处理掉一个安全节点，所有指向它的前驱节点的出度都会减 1，当前驱节点的出度变为 0 时，说明它已经没有“未处理的后继”了，于是可以判定安全。这种“计数删除”是拓扑排序的通用套路，理解它比记住代码更重要。

2.3 为什么这个递推过程不会漏人

可能有读者会担心：从终端节点出发，一层层往回扩散，会不会漏掉某个安全节点？不会，这里可以用最远路径长度来证明。

定义一个安全节点 v 的“安全距离”为从 v 出发，走到某个终端节点的最长路径长度。终端节点的安全距离是 0，其他安全节点的安全距离是它的所有后继节点安全距离最大值再加 1。因为所有路径都有限且能到达终端节点，这个最大值一定存在。

现在看算法：第一轮，所有出度为 0 的节点入队，这正是安全距离为 0 的节点。当距离为 k 的所有节点都处理完之后，那些安全距离为 k+1 的节点会怎样？它们的所有后继节点距离都不超过 k，而且至少存在一个后继距离正好等于 k，所以在这些后继节点的处理过程中，每个后继被遍历到时，前驱节点的出度都会减 1。当一个节点的所有后继都被遍历完，出度归零，它就会入队。换句话说，算法按照安全距离从小到大的顺序，一个不漏地把所有安全节点全部找出来。

这个证明也解释了为什么队列版本天然正确：它其实是在做一个按层扩散的 BFS，每一层对应一个安全距离。剩下的那些最终没能入队的节点，就都是会走进环、或者本身就在环里的节点。

2.4 为什么正着拓扑排序不行

看到“拓扑排序”四个字，很多人会下意识地想做正向拓扑排序：从入度为 0 的节点开始，不断删除节点，最终找不在环上的节点。这道题如果这么做，会得到一个错误答案。

举例说明：0 -> 1，1 -> 2，2 -> 1。正向拓扑排序从 0 开始，0 的入度为 0，队列先弹出它。但 0 的路径最终会进入 1 和 2 组成的环，0 根本不安全。正向拓扑排序只关心“这个节点有没有入边”，它会把一个 DAG 的起始部分全部剥掉，可是本题要求的安全属性是从路径终点反向传播的，两者方向正好相反。

所以这道题看起来是“拓扑排序”，实际做的是“反向拓扑”。反向建图是必须的吗？严格来说，如果不建反向图，也可以用原图的邻接表配合记忆化搜索实现，但那就不是拓扑排序的思路了。建反图的价值在于，把“找所有前驱”这件事从 O(E) 的扫描优化成 O(1) 的邻接表查询，让整个过程变成一趟标准的 BFS。

3. 代码逐行拆解：两个常用版本

3.1 Python 版本：核心代码只有三十行

from collections import deque from typing import List class Solution: def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]: n = len(graph) # rev_graph[v] 中保存所有指向 v 的节点 rev_graph = [[] for _ in range(n)] # out_degree[u] 表示原图中节点 u 还剩下的出边数量 out_degree = [0] * n for u in range(n): for v in graph[u]: rev_graph[v].append(u) out_degree[u] += 1 q = deque() safe = [False] * n for i in range(n): if out_degree[i] == 0: q.append(i) safe[i] = True while q: cur = q.popleft() for pre in rev_graph[cur]: out_degree[pre] -= 1 if out_degree[pre] == 0: safe[pre] = True q.append(pre) return [i for i in range(n) if safe[i]]

这段代码有几个细节值得反复看。首先，节点编号是 0 到 n-1，所以可以开定长数组表示状态。我在写安全节点时用了一个布尔数组 safe，其实完全可以用一个整型数组，语义更丰富，但布尔数组在 Python 里最直观。其次，出度统计一定要放在原图遍历时完成，有些人不小心把它放进反图统计，那统计出来的就是入度不是出度，整个算法就反了。最后，队列初始化的范围是全部节点，不要只遍历一部分，否则终端节点可能漏掉。

3.2 C++ 版本：写法和优化点

#include <vector> #include <queue> using namespace std; class Solution { public: vector<int> eventualSafeNodes(vector<vector<int>>& graph) { int n = (int)graph.size(); vector<vector<int>> rev(n); vector<int> out(n, 0); for (int u = 0; u < n; ++u) { for (int v : graph[u]) { rev[v].push_back(u); ++out[u]; } } queue<int> q; vector<int> safe(n, 0); for (int i = 0; i < n; ++i) { if (out[i] == 0) { q.push(i); safe[i] = 1; } } while (!q.empty()) { int cur = q.front(); q.pop(); for (int pre : rev[cur]) { --out[pre]; if (out[pre] == 0) { safe[pre] = 1; q.push(pre); } } } vector<int> ans; for (int i = 0; i < n; ++i) { if (safe[i]) ans.push_back(i); } return ans; } };

C++ 版本和 Python 版本在结构上没有本质区别，主要差别在于没有 deque 和列表推导式，其他思路一模一样。写 C++ 时有两个容易出错的地方：一是 graph 本身是 vector<vector >，遍历时建议使用引用而非值拷贝，避免复制整个子数组；二是数组 safe 我用 int 而不是 bool，主要是为了代码在其他编译器下表现更稳定，其实 bool 也没有问题。结果数组在最后按索引顺序遍历 safe 数组生成，不需要再做一次 sort，这使得返回结果天然满足题目要求的升序条件。

3.3 复杂度关键点：为什么一趟 BFS 就够

时间复杂度和空间复杂度都需要讲明白。设节点数为 V，边数为 E。建反图时，我们遍历了每条边一次，复杂度 O(V + E)。初始化队列也要扫一遍所有节点，O(V)。BFS 过程中，每个节点最多入队一次、出队一次，而每次出队都要遍历它在反图中的所有入边，这些入边合起来就是原图中的所有边，所以 BFS 的总复杂度也是 O(V + E)。整体时间 O(V + E)。

空间上，反图需要存储所有边，O(E)，出度数组、安全数组、队列各占用 O(V)，总体 O(V + E)。这个复杂度是这类图遍历题的最优级别，因为即使只读一遍输入图，也不可能低于 O(V + E)。对比暴力模拟，每个节点都去做一次 DFS 并判断是否会进入环，最坏情况下会重复遍历大量公共路径，复杂度可以退化到 O(V * (V + E))，拓扑排序的优势非常明显。

4. 另一条路：DFS 三色标记法，选哪个更稳

4.1 三色标记的写法

除了反向拓扑排序，这道题还有另一种经典解法：DFS 三色标记。它的思路是给每个节点维护三种状态：0 表示未访问，1 表示当前正在递归栈中，2 表示已经确认安全。如果 DFS 过程中遇到状态为 1 的节点，说明当前路径上存在环，整条路径都不安全；如果某个节点的所有后继都确认安全，那这个节点本身也确认安全，标记为 2。

from typing import List class Solution: def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]: n = len(graph) color = [0] * n # 0=未访问 1=当前递归栈中 2=已确认安全 ans = [] def dfs(u: int) -> bool: if color[u] == 1: return False if color[u] == 2: return True color[u] = 1 for v in graph[u]: if not dfs(v): return False color[u] = 2 return True for i in range(n): if dfs(i): ans.append(i) return ans

这段代码比拓扑排序更短，因为不需要建反图，直接在原图上做后序遍历。它判断安全的逻辑和拓扑排序本质上是一致的：一个节点安全，当且仅当所有后继安全。区别在于，拓扑排序用队列从终端节点往上推，DFS 用递归从上往下查，然后在回溯过程中把安全信息向上传递。递归栈中遇到状态 1，说明发现了环，这是三色标记最核心的判环机制。

4.2 和拓扑排序的对比与选择

选型建议很简单：如果你在面试现场，并且图是普通规模，DFS 三色标记写起来最快，逻辑也最直观，适合快速交卷。如果图的节点数到十万、百万级别，或者路径可能特别深，DFS 递归很容易触发栈溢出，此时拓扑排序的队列版本更稳。另外，如果你的后续问题需要用到拓扑序列本身，比如按依赖顺序输出节点，那拓扑排序是唯一的选择，DFS 给不了你要的顺序。就我个人而言，做工程题时我优先用拓扑排序，因为队列可控、思路可复用，踩坑概率最小。

5. 刷这道题最容易踩的 5 个坑

5.1 把终端节点理解成入度为 0 的节点

终端节点的定义是“没有出边”，也就是出度为 0。但很多人看图时会下意识找“没有进来的边”，也就是入度为 0 的节点。这两者差远了。入度为 0 的节点可能是整个图的起点，但它后面可能挂着一个环，从它出发照样会走进环里，不安全。一个快速自查方法：在样例里找一个指向环的链头节点，看它是不是入度为 0，如果是，而你又把它当成了终端节点，那你的算法肯定错了。

5.2 用正向拓扑排序求不在环上的点

前一节已经解释过正向拓扑排序为什么不行，这里再强调一下现象。正向拓扑排序最终会把所有入度为 0 的节点依次删掉，如果一个节点入度为 0 但它通向环，它会被错误地标记为可删除。我见过很多代码写成“先求所有环上的点，再反过来取补集”，这种思路在处理“指向环的节点”时会漏判，导致结果比正确答案多出几个节点。所以务必要记住，本题的安全状态依赖方向是“后继决定前驱”，不是“前驱决定后继”。

5.3 自环、重复边、孤立点这些边界情况

自环是一个很简单但容易忽略的边界。节点 5 -> 5，它的出度是 1，不是 0，所以永远不会进入初始队列。而其他指向它的节点，比如 4 -> 5，因为 5 始终无法被确认安全，4 的出度永远减不到 0，所以 4 也不会被误判为安全。拓扑排序处理自环是天然正确的，不需要特殊判断。

重复边在某些测试数据里可能出现。如果一个节点有两条同样的边指向同一个后继，那么出度数组会重复累加。BFS 处理时，这两条边会分别在反图的邻接表里出现，删除两次，最终出度还是能归零，正确性不受影响，只是白白浪费了时间。如果数据量大到影响性能，可以在建图时用集合去重。

孤立节点是最简单的边界：它没有出边，出度为 0，直接进入队列，标记为安全。从它出发没有任何路径，按定义“所有路径最终到达终端节点”是成立的。包含 0 条边的空图也同理，答案应该是全部节点。

5.4 建反图时方向写反

这个错误特别隐蔽。建反图的正确写法是：原图 u -> v 时，在 rev[v] 中加入 u。有人写代码时习惯性写成 rev[u].append(v)，结果得到的还是原图，整道题就变成了在原图上做正向 BFS，答案完全错误。

我在调试时常用的自查方法是拿一个简单样例：若 u 指向 v，v 没有出边，那么正确算法应该先处理 v，然后让 u 的出度减 1 并标记安全。如果你发现自己的 BFS 先弹出的是 u，那一定把图建反了。这种错误用肉眼很难看出来，建议在写完建图后立刻打印一遍 rev 的内容，对照原图确认方向。

5.5 深链图递归爆栈

DFS 三色标记写起来很爽，但 Python 默认递归深度只有 1000 左右。如果题目给了一条 10 万个节点组成的链，递归写法直接栈溢出。改 sys.setrecursionlimit 可以提升限制，但还是有崩溃风险，而且不同运行环境表现不一样。更稳妥的解决方法是把 DFS 改成迭代栈版本，或者直接改用拓扑排序的 BFS。刷题时遇到节点规模超过一万，我默认优先考虑 BFS 拓扑排序，不给自己留爆栈的隐患。

这里整理一个速查表，方便以后复盘。

6. 从这道题延伸开：拓扑排序在真实场景里解决什么问题

6.1 课程编排：先修依赖检测

和本题最接近的经典应用是课程表问题。每门课可能有先修课程，比如数据结构之前要先学程序设计。把每门课看作节点，依赖关系看作有向边，那么拓扑排序就能告诉我们是否存在一种合法的学习顺序。如果图中存在环，说明课程依赖形成了死循环，永远无法学完。课程表问题的实质是“判断全图是否无环”，而 802 题是“找出所有不会碰环的节点”，两者的底层模型几乎完全相同，只是查询目标不同。学会 802 题之后，再去做课程表问题，思路会通得很快。

6.2 死锁检测和银行家算法的血缘关系

操作系统里的资源分配模型也可以化成图：进程和资源是两种节点，进程等待资源时有一条从进程指向资源的边，资源分配给进程时有一条从资源指向进程的边。如果这个图中存在环，就说明发生死锁。反过来，那些不会进入环的进程，等同于本题中的安全节点。

更妙的是银行家算法的安全性检查。它维护每个进程还需要的资源数、系统当前剩余的资源数，每次找一个“当前资源数能满足其最大需求”的进程，假设它执行完并释放资源，然后继续找下一个。这个过程本质上就是“从可完成状态反向扩散”，和本题的“从终端节点反向扩散”如出一辙。拓扑排序的思维一旦建立，很多系统层面的问题都能用它重新认识。

6.3 依赖构建与循环引用检测

前端打包工具、后端构建工具都离不开依赖图。比如项目模块 A 依赖 B，B 依赖 C，C 又依赖 A，构建系统会报循环依赖错误，因为没有任何模块可以被最先构建。而“找出所有能最终被构建成功的模块”和本题“找出所有安全节点”是同一件事：从没有依赖的模块开始，一层层向上，所有依赖都已构建成功的模块也能被构建，最终构建不了的那些模块就是构成了循环依赖环、或者依赖了坏模块的部分。

6.4 通用套路：识别“反向拓扑”题

拿过一道题，怎么快速判断能不能用反向拓扑？我总结了几个特征词：出现了“最终都会到达某个终止状态”“不会进入环”“所有路径都满足某条件”“依赖可达”。只要题目描述里有这些意思，优先想反向建图加出度归零。如果题目只是判断“是否存在环”，那 DFS 三色标记或正向拓扑都可以；如果题目还要输出某些具体的顺序，比如先修顺序、构建顺序，那就必须用拓扑排序。

最后聊一点个人体会。这道题给我最大的收获不是拓扑排序模板，而是“递推方向”这件事。以前我写拓扑排序就是排队选课，看到 802 题才意识到，只要某个状态能由所有后继状态推出，那大概率就要反向建图、从终止状态往前推。后来做死锁检测、依赖环分析，我都习惯先圈出初始安全集，再想状态怎么传播，思路会清晰很多。如果你正在啃图论，我的建议是：别着急背模板，先把谁是终点、谁依赖谁想明白。想明白了，代码几分钟就能写出来。