LeetCode-Go 题解 802：Find Eventual Safe States 安全节点判定与三色 DFS 染色法

LeetCode-Go 题解 802：Find Eventual Safe States 安全节点判定与三色 DFS 染色法

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本题是经典的有向图环检测与节点安全性判定问题，核心在于回答“从某个节点出发，无论沿哪条边走，是否都必然能在有限步内到达终点（出度为 0 的节点）”。本文以 LeetCode 802（Find Eventual Safe States）为切入点，完整讲解题目定义与示例，深入剖析本仓库 LeetCode-Go 中给出的三色 DFS 染色法实现（源码、测试），并附带逐步推演与复杂度分析。读完本文，你将掌握“白色未访问、灰色在栈中、黑色安全”这一可复用的图遍历染色范式，并能直接应用到环检测、课程表、拓扑排序等同类问题中。

一、题目：Find Eventual Safe States（LeetCode 802）

原题完整描述见 leetcode/0802.Find-Eventual-Safe-States/README.md，要点如下：

在一个有向图中，我们从某个节点出发，每一步沿一条有向边行走。如果到达一个终点（terminal，即没有任何出边的节点），我们就停止。

称起始节点是最终安全（eventually safe）的，当且仅当我们必然最终走到一个终点。更严格地说，存在一个自然数K，使得无论沿途如何选择走向，我们都必然在小于 K 步内停在一个终点上。

请找出所有最终安全的节点，并以升序数组返回。

输入形式：有向图共有N个节点，编号为0, 1, ..., N-1，其中N等于graph的长度。graph[i]是标签j的列表，表示存在有向边(i, j)。

示例与图解

Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]] Output: [2,4,5,6]

该图对应的有向边为：0→1、0→2、1→2、1→3、2→5、3→0、4→5。原题中附带了这幅图的示意图（该图托管在 LeetCode 题目站点上，不在此仓库内）。可以这样理解：

• 节点5、6出度均为 0，是终点，天然安全；
• 节点4只有一条出边指向终点5，无论怎么走都会在 1 步内停下，安全；
• 节点2只有一条出边指向5，同样安全；
• 节点0 → 1 → 3 → 0构成一个环，从0、1、3中的任意一点出发都可以无限循环而永远走不到终点，因此0、1、3都不安全；
• 最终安全节点集合为[2, 4, 5, 6]，按升序输出。

约束条件

• graph长度（节点数）不超过10000；
• 图的边数不超过32000；
• 每个graph[i]是升序排列的不同整数列表，取值在[0, graph.length - 1]区间内。

二、解题思路：从“能否到终点”到“是否入环”

先做一个关键等价转化：一个节点不安全，当且仅当从它出发能够进入一个有向环。因为只要路径上存在环，就可以在环内无限绕圈，永远无法满足“小于 K 步必然停止”的条件；反之，如果一个节点不在任何环上，那么从它出发的所有路径都是有限长的（有向图中有限路径必然终止于出度为 0 的终点），必然能在有限步内停下。

因此本题就转化为：找出所有不在任何环中的节点。判定手段有两类主流方法：

1. 拓扑排序 + 反向图：对所有节点做 Kahn 拓扑排序，能进入拓扑序列的节点即不在环中；
2. DFS 三色标记（本仓库采用）：用三种颜色在单次遍历中同时完成“访问中”与“已成环”的判定。

原题解（README.md）明确说明“这一题可以用拓扑排序，也可以用 DFS 染色来解答”，本仓库选择了 DFS 染色方案，下文重点展开。

三、三色 DFS 染色法：原理与语义

DFS 染色法为每个节点维护一个颜色数组color，三种颜色语义如下：

核心逻辑：

• 第一次访问某节点时，将其从白色置为灰色，然后递归搜索它的所有出边邻居；
• 递归过程中若遇到一个灰色节点，说明发现了一条回到“当前栈中节点”的路径，即存在环，此时立即终止搜索并向上返回失败；由于环上所有节点（以及能走到环上的节点）都已经标记为灰色，它们会始终保持灰色，即被判定为不安全；
• 若整棵递归子树搜索完毕都没有遇到灰色节点，则在回溯时把当前节点从灰色改为黑色，表示它不在环中，是安全节点；
• 利用“灰色即不安全”这一性质，可以避免在环上重复递归：当一个节点已经染成灰色时，直接返回false，无需再次展开。

四、Go 实现与源码逐行解析

仓库中的完整实现位于 leetcode/0802.Find-Eventual-Safe-States/802.%20Find%20Eventual%20Safe%20States.go，与题解 README 中给出的代码一致：

func eventualSafeNodes(graph [][]int) []int { res, color := []int{}, make([]int, len(graph)) for i := range graph { if dfsEventualSafeNodes(graph, i, color) { res = append(res, i) } } return res } // colors: WHITE 0, GRAY 1, BLACK 2; func dfsEventualSafeNodes(graph [][]int, idx int, color []int) bool { if color[idx] > 0 { return color[idx] == 2 } color[idx] = 1 for i := range graph[idx] { if !dfsEventualSafeNodes(graph, graph[idx][i], color) { return false } } color[idx] = 2 return true }

逐行拆解

外层主函数eventualSafeNodes：

• color := make([]int, len(graph))：创建颜色数组，Go 切片默认零值即0，正好对应白色（未访问），无需显式初始化；
• 依次以每个节点i为起点调用dfsEventualSafeNodes；
• 返回值true表示该节点安全，追加进结果切片res；
• 由于循环本身按节点编号升序进行，结果天然有序，无需额外排序。

内层递归dfsEventualSafeNodes：

1. if color[idx] > 0：节点已被染过色（灰色或黑色），直接返回“是否为黑色”。这一行同时承担了记忆化与环检测短路两个职责：
   • 黑色节点：返回true，避免重复展开已经验证安全的分支；
   • 灰色节点：返回false，立即向上游传播“遇到环”的信号，且由于灰色节点已被染过色，环上的节点不会再被重复递归，防止无限循环。
2. color[idx] = 1：首次访问，白色变灰色，标记“正在访问/在栈中”。
3. 遍历graph[idx]的所有邻居，递归调用；只要任何一个邻居返回false，当前节点也立即返回false，并且保持灰色——这正是“能从该节点走到环”的不安全语义。
4. 所有邻居都安全后，color[idx] = 2染黑，返回true。

与二分图染色（785）的对比

本仓库另一道图染色题 0785.Is-Graph-Bipartite 同样使用 DFS 染色，但语义不同：785 用“红/绿/未染”三态判断相邻节点是否同色（二分图判定），而 802 的灰色是“递归栈中”的哨兵，用于捕捉后向边形成的环。两者的共同点是都通过一次遍历加颜色数组完成全图判定，可对比学习“同一种技巧在不同问题中的变形”。

五、算法逐步推演（以示例图为例）

对graph = [[1,2],[2,3],[5],[0],[5],[],[]]执行上述代码：

1. 从节点0开始：染灰0，递归邻居1；
2. 染灰1，递归邻居2；
3. 染灰2，递归邻居5；
4. 5无出边，染黑5，返回true；2的所有邻居安全，染黑2，返回true；
5. 1继续递归邻居3：染灰3，递归邻居0；此时发现0是灰色（还在栈中），直接返回false，3保持灰色并返回false，1同样保持灰色返回false，0也保持灰色返回false；
6. 依次对1、2、3、4、5、6重复：1、3已是灰色直接返回false；2已是黑色直接返回true；4 → 5路径安全，染黑4；5、6无出边直接染黑；
7. 最终黑色节点为{2, 4, 5, 6}，按编号顺序输出[2, 4, 5, 6]，与预期一致。

可以看出，灰色标记让环0→1→3→0上的三个节点在首次接触时就全部被判定为不安全，整个算法只对每个节点至多展开一次递归子树。

六、复杂度分析

• 时间复杂度：O(V + E)，其中V为节点数（≤ 10000），E为边数（≤ 32000）。每个节点至多被完整访问一次（染黑），每条边至多被检查一次；已被染色的灰色/黑色节点通过color[idx] > 0分支常数时间返回。
• 空间复杂度：O(V)，来自颜色数组color与递归栈深度（最坏情况下递归深度等于节点数，即退化为一条链时）。

七、测试用例验证

仓库为本题提供了单元测试 802. Find Eventual Safe States_test.go，其结构与其他题解保持一致：

func Test_Problem802(t *testing.T) { qs := []question802{ { para802{[][]int{{1, 2}, {2, 3}, {5}, {0}, {5}, {}, {}}}, ans802{[]int{2, 4, 5, 6}}, }, } // 遍历用例并打印 input/output }

测试通过para802/ans802两个结构体封装输入与期望输出，Test_Problem802遍历用例并调用eventualSafeNodes断言结果。在仓库根目录执行以下命令即可运行测试：

go test -v ./leetcode/0802.Find-Eventual-Safe-States/ -run Test_Problem802

本项目采用 Go 1.19（见 go.mod），测试输出会打印【input】与【output】便于对照验证。

八、延伸：拓扑排序的等价解法

除 DFS 染色外，本题还有经典的拓扑排序解法，可作为交叉验证：

1. 构建反向图（把所有边(i, j)反转成(j, i)）并统计每个节点的出度；
2. 将所有出度为 0 的节点入队（它们都是安全终点）；
3. 反复出队，将反向图中指向它的“前驱”出度减 1，减到 0 则入队；
4. 最终能进入队列的节点即为安全节点。

两种方法的时间复杂度均为O(V + E)。DFS 染色的优势是单次遍历、不需要额外建反向图；拓扑排序的优势是思路直观、与经典 Kahn 算法一脉相承。理解其中一种后，可以很容易写出另一种作为验证。

总结

LeetCode 802 的核心考点是将有向图中的环与安全性判定统一：不在任何环上的节点即为最终安全节点。本仓库给出的三色 DFS 染色实现，用0（白）/ 1（灰）/ 2（黑）三个状态在一个color数组中同时完成了访问标记、递归栈标记与结果缓存，代码简洁且时间复杂度达到最优的O(V + E)。建议读者结合 源码、测试 与 题解文档 自行复现，并尝试用拓扑排序版本对比，从而把“三色染色”这一范式内化为处理环检测类题目的常用工具。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go