LeetCode-Go 题解 802Find 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 802Find Eventual Safe States为切入点完整讲解题目定义与示例深入剖析本仓库 LeetCode-Go 中给出的三色 DFS 染色法实现源码、测试并附带逐步推演与复杂度分析。读完本文你将掌握“白色未访问、灰色在栈中、黑色安全”这一可复用的图遍历染色范式并能直接应用到环检测、课程表、拓扑排序等同类问题中。一、题目Find Eventual Safe StatesLeetCode 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 的终点必然能在有限步内停下。因此本题就转化为找出所有不在任何环中的节点。判定手段有两类主流方法拓扑排序 反向图对所有节点做 Kahn 拓扑排序能进入拓扑序列的节点即不在环中DFS 三色标记本仓库采用用三种颜色在单次遍历中同时完成“访问中”与“已成环”的判定。原题解README.md明确说明“这一题可以用拓扑排序也可以用 DFS 染色来解答”本仓库选择了 DFS 染色方案下文重点展开。三、三色 DFS 染色法原理与语义DFS 染色法为每个节点维护一个颜色数组color三种颜色语义如下颜色值语义判定结果0白色 WHITE尚未被访问未知需要继续搜索1灰色 GRAY正在当前 DFS 递归栈中或已被证实处于环中不安全2黑色 BLACK所有相邻节点都已访问完毕且该节点不在环中安全核心逻辑第一次访问某节点时将其从白色置为灰色然后递归搜索它的所有出边邻居递归过程中若遇到一个灰色节点说明发现了一条回到“当前栈中节点”的路径即存在环此时立即终止搜索并向上返回失败由于环上所有节点以及能走到环上的节点都已经标记为灰色它们会始终保持灰色即被判定为不安全若整棵递归子树搜索完毕都没有遇到灰色节点则在回溯时把当前节点从灰色改为黑色表示它不在环中是安全节点利用“灰色即不安全”这一性质可以避免在环上重复递归当一个节点已经染成灰色时直接返回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 }逐行拆解外层主函数eventualSafeNodescolor : make([]int, len(graph))创建颜色数组Go 切片默认零值即0正好对应白色未访问无需显式初始化依次以每个节点i为起点调用dfsEventualSafeNodes返回值true表示该节点安全追加进结果切片res由于循环本身按节点编号升序进行结果天然有序无需额外排序。内层递归dfsEventualSafeNodesif color[idx] 0节点已被染过色灰色或黑色直接返回“是否为黑色”。这一行同时承担了记忆化与环检测短路两个职责黑色节点返回true避免重复展开已经验证安全的分支灰色节点返回false立即向上游传播“遇到环”的信号且由于灰色节点已被染过色环上的节点不会再被重复递归防止无限循环。color[idx] 1首次访问白色变灰色标记“正在访问/在栈中”。遍历graph[idx]的所有邻居递归调用只要任何一个邻居返回false当前节点也立即返回false并且保持灰色——这正是“能从该节点走到环”的不安全语义。所有邻居都安全后color[idx] 2染黑返回true。与二分图染色785的对比本仓库另一道图染色题 0785.Is-Graph-Bipartite 同样使用 DFS 染色但语义不同785 用“红/绿/未染”三态判断相邻节点是否同色二分图判定而 802 的灰色是“递归栈中”的哨兵用于捕捉后向边形成的环。两者的共同点是都通过一次遍历加颜色数组完成全图判定可对比学习“同一种技巧在不同问题中的变形”。五、算法逐步推演以示例图为例对graph [[1,2],[2,3],[5],[0],[5],[],[]]执行上述代码从节点0开始染灰0递归邻居1染灰1递归邻居2染灰2递归邻居55无出边染黑5返回true2的所有邻居安全染黑2返回true1继续递归邻居3染灰3递归邻居0此时发现0是灰色还在栈中直接返回false3保持灰色并返回false1同样保持灰色返回false0也保持灰色返回false依次对1、2、3、4、5、6重复1、3已是灰色直接返回false2已是黑色直接返回true4 → 5路径安全染黑45、6无出边直接染黑最终黑色节点为{2, 4, 5, 6}按编号顺序输出[2, 4, 5, 6]与预期一致。可以看出灰色标记让环0→1→3→0上的三个节点在首次接触时就全部被判定为不安全整个算法只对每个节点至多展开一次递归子树。六、复杂度分析时间复杂度O(V E)其中V为节点数≤ 10000E为边数≤ 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 染色外本题还有经典的拓扑排序解法可作为交叉验证构建反向图把所有边(i, j)反转成(j, i)并统计每个节点的出度将所有出度为 0 的节点入队它们都是安全终点反复出队将反向图中指向它的“前驱”出度减 1减到 0 则入队最终能进入队列的节点即为安全节点。两种方法的时间复杂度均为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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
