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

◎

本节目标

从终点在反图中传播安全性，以出度拓扑消除找出所有最终安全节点。

这是图论综合中“从终点反向确认”的母题。正向判断某点会不会进入环不易共享信息，而终点的安全性可以沿反图稳定传播。

查看 LeetCode 原题

题意与约束

若从一个节点出发的所有路径最终都会停在出度为零的终点，它是安全节点；能进入任意有向环的节点都不安全。答案按升序返回。孤立节点和所有终点组成的图全安全，纯环没有安全节点。

直接思路与瓶颈

从每个节点分别 DFS，并在每次搜索中判断是否碰到环，会重复遍历大量共享后继，且要区分当前路径与已完成状态。安全性由“所有后继都安全”决定，更适合从已知终点反向批量传播。

图模型与算法推导

保存原图 outdegree[node]，并把每条 node -> nxt 反向为 nxt -> node。所有出度为零的节点先入队。弹出一个安全节点 cur 时，枚举反图前驱 prev 并将其剩余出度减一；降为零说明 prev 的全部原后继都已安全，于是入队。

正确性依据

初始终点显然安全。归纳地，入队节点的每条原出边都已在某个安全后继被处理时删除，因此所有路径只能继续到安全节点并最终终止。未被消除的剩余子图中每个节点仍有一条剩余出边，有限图中持续沿边必进入环，故这些节点不安全。

样例执行过程

对 [[1,2],[2,3],[5],[0],[5],[],[]]，初始出度为 [2,2,1,1,1,0,0]，队列 [5,6]。弹出 5，反图前驱 2,4 的出度分别变为 0,0，队列成为 [6,2,4]；再弹出 2，使 1 从 2 变为 1。6、2、4 之外的 0,1,3 留在环中，最终排序得到 [2,4,5,6]。

代码实现

C++

C++17

#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = static_cast<int>(graph.size());
        vector<vector<int>> reverseGraph(n);
        vector<int> outdegree(n, 0);
        for (int node = 0; node < n; node++) {
            outdegree[node] = static_cast<int>(graph[node].size());
            for (int nxt : graph[node]) {
                reverseGraph[nxt].push_back(node);
            }
        }

        queue<int> pending;
        for (int node = 0; node < n; node++) {
            if (outdegree[node] == 0) {
                pending.push(node);
            }
        }

        vector<int> safe;
        while (!pending.empty()) {
            int cur = pending.front();
            pending.pop();
            safe.push_back(cur);
            for (int prev : reverseGraph[cur]) {
                outdegree[prev]--;
                if (outdegree[prev] == 0) {
                    pending.push(prev);
                }
            }
        }
        sort(safe.begin(), safe.end());
        return safe;
    }
};

Python

Python 3

from collections import deque


class Solution:
    def eventualSafeNodes(self, graph: list[list[int]]) -> list[int]:
        size = len(graph)
        reverse_graph = [[] for _ in range(size)]
        outdegree = [len(neighbors) for neighbors in graph]
        for node, neighbors in enumerate(graph):
            for nxt in neighbors:
                reverse_graph[nxt].append(node)

        pending = deque(node for node in range(size) if outdegree[node] == 0)
        safe: list[int] = []
        while pending:
            cur = pending.popleft()
            safe.append(cur)
            for prev in reverse_graph[cur]:
                outdegree[prev] -= 1
                if outdegree[prev] == 0:
                    pending.append(prev)
        return sorted(safe)

复杂度分析

建反图、每个节点入队和每条边被处理一次，时间 O(V + E)；反图、出度、队列与结果共用 O(V + E) 空间。

边界与易错点

• 维护的是原图出度，不是反图入度。
• 出度必须恰好降到零才能入队。
• “能到达终点”不等于安全，路径也可能分叉到环。
• 队列弹出顺序不保证升序，返回前要排序。

模式迁移

当一个结论依赖“所有后继已满足条件”时，可从基础状态反向减少未完成依赖；它沿用拓扑消除思想，但目标是确认状态而非输出正向拓扑序。