某HR:有人说boss上很多公司都把年龄要求改成了 40、45岁，证明大龄打工人就业环境开始变好，但真相是招个销售、工人都在卡年龄

这道图算法题，别急着从起点往下搜

一个节点明明有三条路，其中两条能走到终点，剩下一条却绕进了环。这个节点算不算安全？

不算。

“找到最终的安全状态”这道题，麻烦的地方就在这里：不是存在一条路能到终点就行，而是从当前节点出发，所有可能经过的路径都必须结束在终点。只要有一条路能钻进环里，这个节点就不安全。

比如下面这张图：

0 -> 1
0 -> 2
1 -> 3
2 -> 3
2 -> 5
3 -> 4
4 -> 3
5

节点 5 没有出边，肯定安全。

节点 3 和节点 4 互相指着，已经成环，不安全。节点 1 会走进节点 3，所以也不安全。节点 2 虽然能走到节点 5，但另一条路会进入环，还是不能算安全。

这题直接用 DFS 做当然可以，不过状态标记稍不注意，就会把“当前搜索路径”和“已经确认不安全”混在一起。我更愿意把图反过来，再跑一次拓扑排序，判断过程更直。

原图中没有出边的节点，就是终点。把所有边反转后，从这些终点开始向前找。某个节点指向的所有节点都已经安全时，它自己才有资格进入安全队列。

Java 代码如下：

classSolution{

public List<Integer> eventualSafeNodes(int[][] graph){
int nodeCount = graph.length;
int[] remainingEdges = newint[nodeCount];

        List<List<Integer>> previousNodes = new ArrayList<>(nodeCount);
for (int i = 0; i < nodeCount; i++) {
            previousNodes.add(new ArrayList<>());
        }

for (int from = 0; from < nodeCount; from++) {
            remainingEdges[from] = graph[from].length;

for (int to : graph[from]) {
                previousNodes.get(to).add(from);
            }
        }

        Deque<Integer> safeQueue = new ArrayDeque<>();
for (int node = 0; node < nodeCount; node++) {
if (remainingEdges[node] == 0) {
                safeQueue.offer(node);
            }
        }

boolean[] safe = newboolean[nodeCount];

while (!safeQueue.isEmpty()) {
int current = safeQueue.poll();
            safe[current] = true;

for (int previous : previousNodes.get(current)) {
                remainingEdges[previous]--;

if (remainingEdges[previous] == 0) {
                    safeQueue.offer(previous);
                }
            }
        }

        List<Integer> answer = new ArrayList<>();
for (int node = 0; node < nodeCount; node++) {
if (safe[node]) {
                answer.add(node);
            }
        }
return answer;
    }
}

remainingEdges 记录的不是反图出度，而是节点在原图中还有多少条边没有被证明安全。

每弹出一个安全节点，就顺着反向边找到它的前驱，并把前驱的剩余出边数减一。只有减到零，才能说明这个前驱的所有去向都安全。

最后没进入队列的节点，大致就两种：自己在环里，或者某条路径最终能进入环。

整套处理只遍历一次节点和边，时间复杂度是 O(V + E)，额外空间也是 O(V + E)。这题看着是在找安全节点，实际做的是一件更干脆的事：从终点反推，把所有能被确认安全的节点一层层剥出来。