LeetCode 802. 找到最终的安全状态
字数 2271 2025-12-18 02:38:22

LeetCode 802. 找到最终的安全状态

这道题描述了一种“安全节点”的概念。题目给定一个有向图，其中包含 n 个节点，节点编号从 0 到 n-1。同时给出一个下标从 0 开始的整数数组 graph，其中 graph[i] 是与节点 i 相邻的节点列表，这意味着从节点 i 到列表中的每个节点都有一条有向边。

我们定义：如果一个节点没有出边（即终端节点），或者从该节点出发的所有路径最终都会到达一个终端节点，那么这个节点就是一个“安全”节点。反之，如果一个节点处于某个环中，或者其路径最终能进入一个环，那么这个节点就是“不安全”的。

你的任务是返回一个由所有安全节点按升序排列的数组。

题目理解与抽象
这道题的核心是判断有向图中的每个节点是否位于环上，或者其路径是否会最终进入环。如果会，则为不安全节点；如果不会，即从该节点出发的所有路径都能到达某个终点（出度为0的节点），则为安全节点。

解题思路分析
我们可以从以下几个角度来思考：

  1. 终点（安全起点）：出度为0的节点，因为没有出边，所以一定是安全的。
  2. 逆推法：如果我们从终点（安全节点）开始，沿着边的反方向进行搜索。如果一个节点的所有后继节点都已经是安全节点，那么这个节点也就变成了安全节点。这个过程很像拓扑排序，但原图中可能存在环，所以我们需要构建一个反图，并在反图上从安全的“终点”出发进行拓扑排序。
  3. 环检测：不安全节点本质上就是那些在环上，或者能走到环上的节点。在反图上进行拓扑排序后，最终无法进入队列（即无法被证明是安全）的节点，就是这些不安全节点。

详细解题过程（拓扑排序法）

步骤1：构建数据结构
我们需要：

  • graph：题目给定的邻接表，表示原图的有向边 u -> v。
  • reverseAdj：反图的邻接表，用于记录 v -> u 的边，即哪些节点指向当前节点。这对于逆推至关重要。
  • inDegree：记录原图中每个节点的出度（而不是入度）。注意，在常规拓扑排序中我们通常用入度，但这里我们是在反图上做“安全节点的传播”，判断一个节点是否安全的条件是“它的所有后继节点都已安全”，这等价于“在反图中，该节点（作为前驱）指向的所有节点都已安全”，而我们需要一个指标来确认“所有后继都已安全”。我们可以用原图的出度作为这个指标，每当一个后继节点被标记为安全，就将当前节点的“未确认后继计数”减1，当减到0时，当前节点就安全了。

步骤2：初始化与准备工作

  • 根据 graph 计算每个节点的出度 outDegree[i]。
  • 同时构建反图 reverseAdj：遍历每个节点 i 和它的每个后继邻居 next，在 reverseAdj[next] 中加入 i。这意味着节点 next 是安全的，可以反过来“通知”它的前驱节点 i。
  • 初始化一个队列 queue，将所有出度为0的节点（即原图的终点，它们肯定是安全的起点）加入队列。

步骤3：拓扑排序（安全节点传播）

  1. 从队列中取出一个节点 node，它一定是安全的。
  2. 遍历 node 在反图中的邻居（即原图中指向 node 的那些前驱节点）prev。
  3. 在逻辑上，节点 prev 有一个后继 node 被确认安全了，所以将 prev 的“未安全后继计数”（即原出度）减1。
  4. 如果 prev 的“未安全后继计数”减到0，说明 prev 的所有后继都已经被确认为安全节点，那么 prev 自身也就成为了安全节点。将其加入队列。
  5. 重复步骤1-5，直到队列为空。

步骤4：收集结果
在整个过程结束后，所有进入过队列的节点，都是安全节点。因为它们要么是初始的终点，要么是其所有后继都最终被证明是安全的节点。这些节点在传播过程中都曾被加入过队列。我们只需要将这些节点收集起来，并按升序排列，即为最终答案。

为什么这个方法有效？
这个过程实质上是在反图上进行拓扑排序，排序的起点是原图中出度为0的节点。在拓扑排序中，能够被排出的节点，意味着在原图中，从它出发不会进入环（否则它的出度不可能被减到0，因为环上的节点互相依赖，出度永不为0）。而无法被排出的节点，就是那些处于环中或能到达环的节点，即不安全节点。

示例说明
假设 graph = [[1,2],[2,3],[5],[0],[5],[],[]]，共7个节点。

  1. 初始化：节点5和6出度为0，是初始安全节点，加入队列。构建反图（例如，节点0指向节点1和2，所以在反图中，节点1和节点2的列表中都包含节点0）。
  2. 传播：
    • 处理节点5：反图中指向5的有节点2和4。将节点2和4的“未确认计数”减1。节点2的计数从2（指向3和5）减为1，节点4的计数从1（指向5）减为0。节点4计数为0，变为安全，入队。
    • 处理节点6：反图中指向6的节点为空，无操作。
    • 处理节点4：反图中指向4的节点为空，无操作。
    • （队列已空，但节点2计数为1，不为0，说明它有一个后继还未被确认为安全，这个后继是节点3。而节点3的后继是节点0，节点0的后继是节点1和2，形成了一个环 2->3->0->2）
  3. 结果：进入过队列的节点是 [5, 6, 4]，排序后为 [4, 5, 6]。它们是安全节点。节点0,1,2,3位于环上或其路径进入环，是不安全节点。

这个过程避免了直接的深度优先搜索中可能遇到的重复访问和状态记录问题，通过拓扑排序清晰地分离出了安全与不安全的节点。

LeetCode 802. 找到最终的安全状态 这道题描述了一种“安全节点”的概念。题目给定一个有向图，其中包含 n 个节点，节点编号从 0 到 n-1。同时给出一个下标从 0 开始的整数数组 graph ，其中 graph[i] 是与节点 i 相邻的节点列表，这意味着从节点 i 到列表中的每个节点都有一条有向边。 我们定义： 如果一个节点没有出边（即终端节点），或者从该节点出发的所有路径最终都会到达一个终端节点，那么这个节点就是一个“安全”节点 。反之，如果一个节点处于某个环中，或者其路径最终能进入一个环，那么这个节点就是“不安全”的。 你的任务是返回一个由所有安全节点按升序排列的数组。 题目理解与抽象 这道题的核心是判断有向图中的每个节点是否位于环上，或者其路径是否会最终进入环。如果会，则为不安全节点；如果不会，即从该节点出发的所有路径都能到达某个终点（出度为0的节点），则为安全节点。 解题思路分析 我们可以从以下几个角度来思考： 终点（安全起点） ：出度为0的节点，因为没有出边，所以一定是安全的。 逆推法 ：如果我们从终点（安全节点）开始，沿着边的 反方向 进行搜索。如果一个节点的 所有后继节点 都已经是安全节点，那么这个节点也就变成了安全节点。这个过程很像拓扑排序，但原图中可能存在环，所以我们需要构建一个 反图 ，并在反图上从安全的“终点”出发进行拓扑排序。 环检测 ：不安全节点本质上就是那些在环上，或者能走到环上的节点。在反图上进行拓扑排序后，最终无法进入队列（即无法被证明是安全）的节点，就是这些不安全节点。 详细解题过程（拓扑排序法） 步骤1：构建数据结构 我们需要： graph ：题目给定的邻接表，表示原图的有向边 u -> v 。 reverseAdj ：反图的邻接表，用于记录 v -> u 的边，即哪些节点指向当前节点。这对于逆推至关重要。 inDegree ：记录原图中每个节点的出度（而不是入度）。注意，在常规拓扑排序中我们通常用入度，但这里我们是在反图上做“安全节点的传播”，判断一个节点是否安全的条件是“它的所有后继节点都已安全”，这等价于“在反图中，该节点（作为前驱）指向的所有节点都已安全”，而我们需要一个指标来确认“所有后继都已安全”。我们可以用原图的出度作为这个指标，每当一个后继节点被标记为安全，就将当前节点的“未确认后继计数”减1，当减到0时，当前节点就安全了。 步骤2：初始化与准备工作 根据 graph 计算每个节点的出度 outDegree[i] 。 同时构建反图 reverseAdj ：遍历每个节点 i 和它的每个后继邻居 next ，在 reverseAdj[next] 中加入 i 。这意味着节点 next 是安全的，可以反过来“通知”它的前驱节点 i 。 初始化一个队列 queue ，将所有出度为0的节点（即原图的终点，它们肯定是安全的起点）加入队列。 步骤3：拓扑排序（安全节点传播） 从队列中取出一个节点 node ，它一定是安全的。 遍历 node 在反图中的邻居（即原图中指向 node 的那些前驱节点） prev 。 在逻辑上，节点 prev 有一个后继 node 被确认安全了，所以将 prev 的“未安全后继计数”（即原出度）减1。 如果 prev 的“未安全后继计数”减到0，说明 prev 的所有后继都已经被确认为安全节点，那么 prev 自身也就成为了安全节点。将其加入队列。 重复步骤1-5，直到队列为空。 步骤4：收集结果 在整个过程结束后，所有进入过队列的节点，都是安全节点。因为它们要么是初始的终点，要么是其所有后继都最终被证明是安全的节点。这些节点在传播过程中都曾被加入过队列。我们只需要将这些节点收集起来，并按升序排列，即为最终答案。 为什么这个方法有效？ 这个过程实质上是 在反图上进行拓扑排序，排序的起点是原图中出度为0的节点 。在拓扑排序中，能够被排出的节点，意味着在原图中，从它出发不会进入环（否则它的出度不可能被减到0，因为环上的节点互相依赖，出度永不为0）。而无法被排出的节点，就是那些处于环中或能到达环的节点，即不安全节点。 示例说明 假设 graph = [[1,2],[2,3],[5],[0],[5],[],[]] ，共7个节点。 初始化 ：节点5和6出度为0，是初始安全节点，加入队列。构建反图（例如，节点0指向节点1和2，所以在反图中，节点1和节点2的列表中都包含节点0）。 传播 ： 处理节点5：反图中指向5的有节点2和4。将节点2和4的“未确认计数”减1。节点2的计数从2（指向3和5）减为1，节点4的计数从1（指向5）减为0。节点4计数为0，变为安全，入队。 处理节点6：反图中指向6的节点为空，无操作。 处理节点4：反图中指向4的节点为空，无操作。 （队列已空，但节点2计数为1，不为0，说明它有一个后继还未被确认为安全，这个后继是节点3。而节点3的后继是节点0，节点0的后继是节点1和2，形成了一个环 2->3->0->2 ） 结果 ：进入过队列的节点是 [5, 6, 4] ，排序后为 [4, 5, 6] 。它们是安全节点。节点0,1,2,3位于环上或其路径进入环，是不安全节点。 这个过程避免了直接的深度优先搜索中可能遇到的重复访问和状态记录问题，通过拓扑排序清晰地分离出了安全与不安全的节点。