LeetCode 802：反向图拓扑排序求解最终安全状态

1. 先把"安全节点"翻译成能动手的条件

做图论题最怕题目绕。像"最终安全状态"这种名字，第一眼完全猜不出要干嘛。把题面拆开其实就两句话：一个节点没有出边，叫终端节点；从某个节点出发，沿着它的所有可能路径一直往前走，如果不管怎么走都必定在有限步内停在某个终端节点上，这个节点就叫安全节点。以前在状态机和程序分析相关内容里接触过类似的"总能停机"概念，所以第一次看到这个定义还觉得挺亲切，但真正动手才发现里面的坑比表面多。这篇文章就只讲第 802 题的拓扑排序解法，从定义、反向建图、代码实现到边界情况一次说完，适合刚学会拓扑排序想拿图论题练手的人，也适合面试前临时捡重点准备的人。

1.1 终端节点只是起点，环才是真正的敌人

终端节点很好理解：出度为 0 的节点，走到它那里就停下来了。如果图里只有一条从 0 到 1 的边，1 没有出边，那 1 是终端节点，0 是安全节点，这个例子谁都会做。可一旦图里有环，情况立刻复杂。考虑一个节点 2，它有一条边指向 3，而 3 是终端节点，同时 2 还有一条边回到 1，1 又回到 2。2 虽然存在一条通往终点的路径，但也存在一条永远绕圈的路径。按照定义，2 不安全，因为"所有路径"这个条件是全称量词，只要有一条路径不终止，整个节点就不安全。这是整道题第一个容易忽略的关键：安全性要求的是"每一条路都必须走到终端"，不是"有机会走到终端"。

顺着这个思路继续想，判断一个节点安不安全，其实是在判断它能不能到达环。环上的节点显然不安全，因为从环上任一点出发都能沿着环无限绕下去，永远到不了没有出边的终端节点。更隐蔽的是环外的节点：只要存在一条边把它接到环上，这个节点也不安全。从它出发可以选择走这条边，一旦进了环就出不来。反过来讲，如果一个节点不在环上，并且所有出边都指向那些最终能到终端的节点，那它就是安全的。到这里，已经可以提炼出一个能在程序里表达的递推条件。

1.2 从定义里抽出一个可迭代的递推条件

稍微形式化一点。记 S 为安全节点集合，节点 u 属于 S 必须满足：要么 u 本身是终端节点；要么 u 的所有出边指向的节点都属于 S。这个条件和动态规划很像，区别在于图里可能有环，不能简单按拓扑顺序从后往前算，因为环会让节点互相依赖，谁都不敢先下结论。拓扑排序正好擅长处理这种"环会破坏依赖顺序"的问题。它不会想办法绕过环，而是通过不断删除入度为 0 的节点，把环暴露出来。但这里有个方向问题：安全性是从终端节点往上游传播的，先确认终端节点安全，然后只有当某个节点的全部出边都指向已确认安全的节点，它才跟着被确认。这个传播方向逆着原图边方向，所以要处理的不是原图，而是反向图。

2. 反向建图的理由：为什么偏要"倒着剥"

2.1 直接跑一遍经典拓扑排序为什么不干净

Kahn 算法大家都很熟：统计入度，把入度为 0 的节点入队，弹出后把它所有邻居的入度减一，减到 0 就继续入队。跑完还剩节点没被处理，说明图里有环。有人会觉得，那直接在原图上跑一遍 Kahn，剩下的节点不就是环？问题在于，安全节点的集合比"环上节点"更大，还要包含所有能走到环的节点。这部分节点在原图 Kahn 算法里的表现并不稳定，可能因为入度为 0 被提前删掉，也可能因为某个边指向环而留在最后，总之不能直接给结论。更根本的原因是，原图上哪类节点一定安全？没有出边的终端节点。终端节点的特征是出度为 0，不是入度为 0。Kahn 算法消耗的度数是入度，这和题目要判断的出度根本不匹配。

让工具和问题匹配的常规做法，就是把边全部反过来。反转之后，原来的出度变成入度，原来的终端节点变成入度为 0 的节点，正好能放进 Kahn 算法的起始队列。这一下就把思考方向理顺了：不是从"起点"往下找终点，而是从"终点"倒着把安全区域一层层扩出来。

2.2 反向图把"出度"难题转成了"入度"判断

在反向图里，原图边 u→v 变成 v→u。终端节点在原图出度是 0，对应到反向图就是没有入边，所以入度是 0。于是问题变成：在反向图里不断删除入度为 0 的节点，删除顺序就是安全节点的确认顺序。为什么删除一个节点 v 之后要去看 v 的反向邻居 u？因为反向邻居意味着原图里有 u→v。当 v 被确认为安全节点，u 的出边里就少了一条"未确认"的边；如果 u 的所有出边指向的节点都被确认安全，u 在反向图里的入度就恰好在此时归零，可以入队。整个删除过程完全是在反向图上做标准 Kahn 算法，只是边方向和题面给的相反。

从这里也能严谨解释为什么算法不会误判环上的节点：环里的每个节点在反向图里都至少有一条来自环内其他节点的入边。只有当环内某个节点先被删除，这条入边才会被消耗，可环内没有任何节点满足入度为 0 的起步条件，所以整个环的所有节点都不会入队，自然不会被标记为安全。它们会一直留在队列外，最后收集答案时直接跳过就好。

2.3 用一张表理清原图和反向图的关系

表格第三行很多人转不过弯：为什么统计反图入度就等于统计原图出度？因为反图里节点 u 的入边，恰好就是原图里从 u 出发的边反转过来的。建反图的时候每遇到一条 u→v，就给 u 的反图入度加 1，同时把它记到 v 的反向邻接表里。代码里这两件事经常写在同一行，也最容易写错，下一节展开讲。

3. 完整代码与逐行注释：反向图 + 入度裁剪

3.1 建图阶段最容易写错的一行

直接上 Java 实现。代码不长，但每一行都有讲究。

public List<Integer> eventualSafeNodes(int[][] graph) { int n = graph.length; List<List<Integer>> rev = new ArrayList<>(); for (int i = 0; i < n; i++) rev.add(new ArrayList<>()); int[] indegree = new int[n]; for (int u = 0; u < n; u++) { for (int v : graph[u]) { rev.get(v).add(u); indegree[u]++; } } Queue<Integer> queue = new LinkedList<>(); for (int i = 0; i < n; i++) { if (indegree[i] == 0) queue.offer(i); } boolean[] safe = new boolean[n]; while (!queue.isEmpty()) { int u = queue.poll(); safe[u] = true; for (int p : rev.get(u)) { indegree[p]--; if (indegree[p] == 0) queue.offer(p); } } List<Integer> ans = new ArrayList<>(); for (int i = 0; i < n; i++) { if (safe[i]) ans.add(i); } return ans; }

这段代码最坑的位置在第二层循环里，同时出现了indegree[u]++和rev.get(v).add(u)两条语句。很多人会习惯性写成indegree[v]++，因为在邻接表里遍历邻居时，自然想到给邻居加度数。可这里维护的是反向图里 u 的入度，也就是原图中 u 的出度。写的时候心里默念：对于每条原图边 u→v，v 反向连回 u，v 收到了一个待确认的前驱 u，同时 u 增加一个入度。这样念几遍就不容易写错。

其他细节：如果图稀疏，用List<List<Integer>>足够；如果想省一点点内存，可以第一遍统计边数再分配数组，但一般用不到这种优化。boolean[] safe只负责记录哪些节点被弹出过，它不等同于输出顺序，最后必须单独收集答案。

3.2 队列剥离阶段为什么能保证不漏

主循环的逻辑一句话就能概括：谁的安全状态被最终确认，就把这个消息传给所有原图中指向它的节点。反向邻接表rev.get(u)正好存了这批节点。每传一次消息，对应的indegree[p]就减 1，因为 p 指向 u 的这条出边已经从"未知"变成"已知安全"。当indegree[p]归零时，p 的全部出边所指向的节点都已经安全，p 自己也安全，可以入队。这个递归式推导正好对应前面说的递推条件：如果所有下游都安全，那么上游才安全。因为消息只沿着反方向传播，永远不可能从安全节点传回环里，所以环上节点会被自动排除。

走一个具体的例子。有向图节点编号 0 到 6，出边如下：

0 → 1, 0 → 2 1 → 2, 1 → 3 2 → 5 3 → 0 4 → 5 5, 6 是终端节点

这个图里，5 和 6 是终端节点，直接安全；2 唯一出边指向 5，所以 2 安全；4 唯一出边指向 5，所以 4 安全。节点 0、1、3 构成一个环 0→1→3→0。虽然 0 有一条边指向 2，能通向安全节点，但 0 还有路径可以进环，所以 0 不安全，1 和 3 同理。最终答案应该是 [2,4,5,6]。

手动模拟一遍算法过程：

• 初始入度数组：indegree[0]=2，indegree[1]=2，indegree[2]=1，indegree[3]=1，indegree[4]=1，indegree[5]=0，indegree[6]=0。
• 初始队列：[5,6]。
• 弹出 5，标记 safe[5]=true。反向邻居是 2 和 4，所以 indegree[2] 变 0，入队；indegree[4] 变 0，入队。
• 弹出 6，标记 safe[6]=true，它没有反向邻居。
• 弹出 2，标记 safe[2]=true。反向邻居是 0 和 1，所以 indegree[0] 从 2 变 1，indegree[1] 从 2 变 1，都还没到 0，不入队。
• 弹出 4，标记 safe[4]=true，它没有反向邻居。
• 队列为空，safe 数组里为 true 的是 2、4、5、6，按下标收集得到 [2,4,5,6]。

从模拟里能清楚看到，0 和 1 的入度都因为 2 被确认而减过 1，但还各剩 1。剩下那条入度分别来自 3 和 0，而 3 在环里永远无法被弹出，所以 0 和 1 也一直卡着。这正是"通向环的节点不安全"在算法运行中的直接体现。

3.3 关于要不要真的修改原图

看到"删除节点"四个字，有人会下意识想真的把图结构改掉：删边、删邻接表、甚至复制一张图。其实完全没必要。反向图建好之后，用入度数组模拟删除就够了。所谓删除，在代码里只体现为某个节点的入度减 1；当一个节点入度归零被弹出来，它不会再去影响别的地方。原图可以一直保持原样，不需要额外修改数据结构。这也是为什么很多题解把这个方法叫"反图拓扑"，因为它真的是在反向图上完整跑了一遍 Kahn 算法。

4. 另一种解法 DFS 三色标记：证明思路的互证

4.1 DFS 三色标记的实现

这个题最常见的另一类解法是 DFS 加三色标记。状态 0 表示未访问，状态 1 表示正在递归栈中，状态 2 表示已经确认安全。如果递归过程中碰上状态为 1 的节点，说明从一个节点出发又绕回到了自己，存在环，那么当前这条搜索路径上的节点都不安全；如果某个节点的所有后继最终都返回安全，那这个节点就是安全的。代码很短，也很有美感：

public List<Integer> eventualSafeNodes(int[][] graph) { int n = graph.length; int[] state = new int[n]; List<Integer> ans = new ArrayList<>(); for (int i = 0; i < n; i++) { if (dfs(i, graph, state)) ans.add(i); } return ans; } private boolean dfs(int u, int[][] graph, int[] state) { if (state[u] != 0) return state[u] == 2; state[u] = 1; for (int v : graph[u]) { if (!dfs(v, graph, state)) return false; } state[u] = 2; return true; }

状态 2 在这里同时承担了记忆化的职责，每个节点最多完整递归一次，所以整体时间复杂度还是 O(V+E)。三色标记比反图拓扑更符合直觉，因为它直接模拟"从当前节点出发能不能找到环"这个过程。但它要求先理解递归终止条件和状态缓存之间的关系，不然很容易写出死循环或者漏判断的状态更新。

4.2 两种方法用哪个：复杂度与风险对比

两种解法的时间复杂度完全相同，都是 O(V+E)，空间也都需要存储邻接信息和辅助数组。真正需要权衡的是下面几点：

• 递归深度：三色标记用递归实现，如果图是一条特别长的链，递归深度会等于节点数。在本机没问题，但在某些判题环境里，深度到几万时默认栈可能不够用。反图拓扑是纯队列迭代，没有递归栈风险。
• 代码量：三色标记更短，十几行就够；反图拓扑需要额外建反向图，第一次写的时候容易在入度统计上犯迷糊。
• 思维成本：三色标记把安全定义直接翻译成 DFS 过程；反图拓扑需要先接受"反向建图 + 入度清零"的转换，一旦想通，适用范围反而更大。

我不觉得这两种方法非得二选一。三色标记里的"状态 2"本质上就是反图拓扑里被剥离节点的集合，前者用递归栈隐式判断环，后者用入度清零显式剥出安全集合。把两种解法都写一遍，对"环"和"安全状态"的理解会立刻立体起来。面试时如果时间紧张，我倾向反图拓扑；如果只是日常写题想快速验证思路，三色标记更顺手。

5. 边界情况、正确性证明和面试表达

5.1 自环、孤立节点和答案排序

自环是典型边界条件。一个节点如果有一条边指向自己，不管它还有多少条通往终端节点的边，它都不安全，因为从它出发可以选择一直绕自己。在反图拓扑里，自环会让入度包含来自自己的一份，这份入度永远无法因为其他节点被剥离而消失。只有在节点自己被弹出时才会消费自己的自环边，可它自己恰恰因为入度不为 0 永远无法弹出，于是自环节点一定会留在安全集合之外。

孤立节点恰好相反。一个节点什么出边都没有，入度为 0，初始就会进队列并马上被标记为安全，这在定义上也讲得通：没有出边，本身就是终端节点。答案排序也值得单独提一下，队列弹出的顺序取决于图的结构，不是按节点编号有序的。如果把队列处理顺序直接当成结果返回，测试用例一多就会出错。这道题要求最终答案按节点编号从小到大排列，所以先标记安全节点，再按索引顺序统一收集是最稳妥的。

5.2 用三条引理向面试官讲清楚正确性

面试时只丢一句"用反图拓扑"是不够的，最好能把正确性讲成一个简短的论证过程。

第一，终端节点在原图出度为 0，一定安全。第二，如果节点 u 的所有出边指向的节点都安全，那么从 u 出发的任意路径第一步会落到某个安全邻居 v，v 的所有路径最终都能走到终端，所以 u 也安全。第三，反过来，只要 u 有一条出边指向不安全节点 v，从 u 出发就能选择这条边进入 v，再沿 v 的某条不终止路径走下去，所以 u 不安全。

这三条合起来正好说明：安全节点集合，就是从终端节点出发、沿着反方向边不断向外扩展能得到的集合。反图 Kahn 算法做的就是这个事：先放入所有终端节点，再逐层加入所有出边都已被确认的节点，直到没有任何新节点可以被加入。剩下的节点全部不安全。这段论证既严谨又简短，在面试里能讲清楚的人，通常对图论基础掌握得都比较扎实。

5.3 顺势记住这一类题的通用套路

这道题值得吸收的不是代码，而是"从哪一端开始剥离"的判断经验。判断条件和终点有关，优先考虑反图；判断条件和起点有关，优先考虑原图拓扑排序。拿不准的时候，画一个带环的小图手动跑一遍，基本就能确定方向。以后碰到"找出所有能到达终点的节点""找出所有环外节点""求哪些节点必然能走到某个安全节点"这些变体，都能用同一套反图拓扑来解。

最后分享一个我自己写题时的习惯：图论题先想递归会不会爆栈，再想迭代能不能做。第 802 题的反图拓扑解法就是个很好的例子，它没有用到递归，却把传统 Kahn 算法的思想完全迁移过来了。把"反着看问题"练成本能之后，很多一开始觉得很绕的图论题都会变得直白很多。