找到最终的安全状态 图解题解

这道题到底在问什么

输入

graph = [[1,2],[2,3],[5],[0],[5],[],[]]

输出

[2,4,5,6]

输入

graph = [[],[0,2,3,4],[3],[4],[]]

输出

[0,1,2,3,4]

最优解：一步一步想明白

1. 3踩进环 = 不安全想象在迷宫里走：只要有一条岔路会把你带进鬼打墙的环，这个起点就危险；条条大路都能走出去才算安全。
2. 4出度 0 必安全正着判断「每条路都通终点」很绕。倒过来想：终点一定安全；谁的所有出边都指向安全点，谁就也安全。像剥洋葱一样从外往里认。
3. 5出度归零 → 安全 → 入队这就是反向拓扑排序：正图看「出度」，沿反图回传消息。出度被削成 0 的点，代表它能去的全是安全点，于是它转正。下面一帧削一条边地演给你看。
4. 6graph=[[1,2],[2,3],[5],[0],[5],[],[]]先看清这张有向图。注意左边 0→1→3→0 转了一个圈（环），右边 5、6 没有出边（终点）。箭头方向就是「能走到哪」。
5. 7出度=0 的是 5 和 6给每个点数出度（头顶数字 = 还有几条出边）。5 和 6 出度为 0，它们是终点、天然安全，先排队等着「转正」。
6. 8q=[5,6]把出度为 0 的 5、6 放进队列（蓝色），准备逐个「确认安全」。队列里的点都是已知能停下的，接下来用它们去削别人的出度。
7. 9弹出 5 · 谁指向 5？弹出 5（橙色高亮 = 正在处理），它确认安全。看反图：2 和 4 都指向 5（两条高亮边），通知它俩「你的出边 5 已安全」。
8. 10out[2]:1→0, out[4]:1→02 和 4 各自只剩这一条出边，被削后出度都变成 0！说明它们能去的（只有 5）已全安全 → 2、4 也安全，入队。5 转绿（已确认）。
9. 11弹出 6 · 反图为空弹出 6（橙色），确认安全。反图里没有点指向 6（没人能走到 6），无需通知谁。队列继续往下处理 2、4。
10. 12out[0]:2→1, out[1]:2→1（未归 0）弹出 2，确认安全。反图：0、1 都指向 2（高亮）。削掉后 out[0]=1、out[1]=1，都还没到 0——它们还有别的出边没确认，先不入队。
11. 13弹出 4 · 反图为空 · q=[]弹出 4，确认安全。没人指向 4，无需回传。队列空了——能确认的都确认完了。剩下 0、1、3 始终没被削到 0。
12. 14out[0]=1,out[1]=1,out[3]=1 ≠ 00、1、3 的出度永远卡在 1，归不了 0——因为 0→1→3→0 是个环（高亮），它们互相指着对方，谁也等不到对方先安全。它们不安全。
13. 15返回 [2,4,5,6]绿色的就是安全点，按确认顺序是 5、6、2、4。从小到大排好序 → [2,4,5,6]。0、1、3 被环困住，不在内。
14. 16白=未访 灰=在栈 黑=安全反图拓扑是「从终点往回认」，三色 DFS 是「往前探、撞到灰点=遇环」。两种殊途同归，下面用三色再演一眼最经典的「撞灰」瞬间。
15. 170 灰（在递归栈）从 0 出发，把它压进递归栈、染灰（橙，表示「正卡在递归里」）。沿第一条出边 0→1 往下探。
16. 180、1 灰走 0→1（高亮），1 没访问过，压栈染灰。栈里现在是 0、1。继续从 1 沿出边 1→3 深入。
17. 190、1、3 灰（在递归栈）走 1→3（高亮），3 也压栈染灰。0、1、3 全在栈里。接着 3 要走它唯一的出边 3→0……
18. 200 是灰 = 撞上环 → 不安全3 沿 3→0（高亮）走，发现 0 还是灰的（还在栈里）——这就是撞上了正在走的环！于是这条链上 0、1、3 全部判定不安全。
19. 21环上三点确定不安全撞灰后回溯：0、1、3 依次退栈，都标记为不安全（恢复成普通色，永不染黑）。它们卡在高亮的环 0→1→3→0 上。
20. 222、4、5、6 全部出边通终点 → 黑而 2→5、4→5（高亮）只通向终点 5（黑/安全），6 本身是终点：它们的出边都不踩灰 → 染黑（安全）。结论和反图拓扑完全一致：[2,4,5,6]。
21. 23graph=[[],[0,2,3,4],[3],[4],[]]换个图练手：1 指向所有点，但整张图没有任何环。先数出度——0 和 4 出度为 0，是终点。
22. 24q=[0,4]，弹出后削前驱0、4 确认安全（绿）。沿反图回传：4 通知前驱 3（边 3→4 高亮），out[3] 削到 0 → 3 入队。1 也被削但还剩 3 条边。
23. 253 安全 → 2 归零入队3 确认安全（绿），通知它唯一前驱 2（边 2→3 高亮），out[2] 归 0 → 2 入队。链条像推骨牌一样一节节往回认。
24. 26返回 [0,1,2,3,4]2 安全后再削 1，out[1] 终于归 0，1 也安全。没有环的图，所有点最终都安全 → [0,1,2,3,4]。对照例一：环是唯一让点不安全的原因。
25. 29反图 + 出度归零拓扑记住这个变形：普通拓扑排序削入度，本题削出度、并且要反着建图来回传消息。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from collections import deque
class Solution:
    def eventualSafeNodes(self, graph):
        n = len(graph)
        rev = [[] for _ in range(n)]
        outdeg = [0] * n          # 每个点的出度
        for u in range(n):
            for v in graph[u]:
                rev[v].append(u)  # 反图：v 记下谁指向它
                outdeg[u] += 1
        q = deque(i for i in range(n) if outdeg[i] == 0)
        safe = [False] * n
        while q:
            x = q.popleft()
            safe[x] = True            # 出度 0 → 安全
            for u in rev[x]:          # 通知指向 x 的点
                outdeg[u] -= 1
                if outdeg[u] == 0:
                    q.append(u)
        return [i for i in range(n) if safe[i]]

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<vector<int>> rev(n);
        vector<int> outdeg(n, 0);
        for (int u = 0; u < n; u++) {
            for (int v : graph[u]) {
                rev[v].push_back(u);
                outdeg[u]++;
            }
        }
        queue<int> q;
        for (int i = 0; i < n; i++)
            if (outdeg[i] == 0) q.push(i);
        vector<bool> safe(n, false);
        while (!q.empty()) {
            int x = q.front(); q.pop();
            safe[x] = true;
            for (int u : rev[x]) {
                if (--outdeg[u] == 0) q.push(u);
            }
        }
        vector<int> ans;
        for (int i = 0; i < n; i++)
            if (safe[i]) ans.push_back(i);
        return ans;
    }
};

class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        List<List<Integer>> rev = new ArrayList<>();
        for (int i = 0; i < n; i++) rev.add(new ArrayList<>());
        int[] outdeg = new int[n];
        for (int u = 0; u < n; u++) {
            for (int v : graph[u]) {
                rev.get(v).add(u);
                outdeg[u]++;
            }
        }
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++)
            if (outdeg[i] == 0) q.offer(i);
        boolean[] safe = new boolean[n];
        while (!q.isEmpty()) {
            int x = q.poll();
            safe[x] = true;
            for (int u : rev.get(x)) {
                if (--outdeg[u] == 0) q.offer(u);
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i++)
            if (safe[i]) ans.add(i);
        return ans;
    }
}

复杂度

面试官可能追问