找到最终的安全状态

什么点不安全？：想象在迷宫里走：只要有一条岔路会把你带进鬼打墙的环，这个起点就危险；条条大路都能走出去才算安全。

换个角度：从终点倒推：正着判断「每条路都通终点」很绕。倒过来想：终点一定安全；谁的所有出边都指向安全点，谁就也安全。像剥洋葱一样从外往里认。

优解：反图 + 拓扑排序：这就是反向拓扑排序：正图看「出度」，沿反图回传消息。出度被削成 0 的点，代表它能去的全是安全点，于是它转正。下面一帧削一条边地演给你看。

例一 · 摆好图：先看清这张有向图。注意左边 0→1→3→0 转了一个圈（环），右边 5、6 没有出边（终点）。箭头方向就是「能走到哪」。

数出度 · 标终点：给每个点数出度（头顶数字 = 还有几条出边）。5 和 6 出度为 0，它们是终点、天然安全，先排队等着「转正」。

5、6 出度 0 · 入队：把出度为 0 的 5、6 放进队列（蓝色），准备逐个「确认安全」。队列里的点都是已知能停下的，接下来用它们去削别人的出度。

确认 5 安全 · 沿反图回传：弹出 5（橙色高亮 = 正在处理），它确认安全。看反图：2 和 4 都指向 5（两条高亮边），通知它俩「你的出边 5 已安全」。

削 2、4 出度 · 都归 0：2 和 4 各自只剩这一条出边，被削后出度都变成 0！说明它们能去的（只有 5）已全安全 → 2、4 也安全，入队。5 转绿（已确认）。

确认 6 安全 · 没人指向它：弹出 6（橙色），确认安全。反图里没有点指向 6（没人能走到 6），无需通知谁。队列继续往下处理 2、4。

确认 2 安全 · 削 0、1：弹出 2，确认安全。反图：0、1 都指向 2（高亮）。削掉后 out[0]=1、out[1]=1，都还没到 0——它们还有别的出边没确认，先不入队。

确认 4 安全 · 队列见底：弹出 4，确认安全。没人指向 4，无需回传。队列空了——能确认的都确认完了。剩下 0、1、3 始终没被削到 0。

剩下的 0、1、3 · 困在环里：0、1、3 的出度永远卡在 1，归不了 0——因为 0→1→3→0 是个环（高亮），它们互相指着对方，谁也等不到对方先安全。它们不安全。

例一收工 · 安全点：绿色的就是安全点，按确认顺序是 5、6、2、4。从小到大排好序 → [2,4,5,6]。0、1、3 被环困住，不在内。

另一视角：三色 DFS：反图拓扑是「从终点往回认」，三色 DFS 是「往前探、撞到灰点=遇环」。两种殊途同归，下面用三色再演一眼最经典的「撞灰」瞬间。

三色 DFS · 0 进栈染灰：从 0 出发，把它压进递归栈、染灰（橙，表示「正卡在递归里」）。沿第一条出边 0→1 往下探。

三色 DFS · 1 进栈染灰：走 0→1（高亮），1 没访问过，压栈染灰。栈里现在是 0、1。继续从 1 沿出边 1→3 深入。

三色 DFS · 3 进栈染灰：走 1→3（高亮），3 也压栈染灰。0、1、3 全在栈里。接着 3 要走它唯一的出边 3→0……

三色 DFS · 3→0 撞到灰！：3 沿 3→0（高亮）走，发现 0 还是灰的（还在栈里）——这就是撞上了正在走的环！于是这条链上 0、1、3 全部判定不安全。

三色 DFS · 0、1、3 退栈判不安全：撞灰后回溯：0、1、3 依次退栈，都标记为不安全（恢复成普通色，永不染黑）。它们卡在高亮的环 0→1→3→0 上。

三色 DFS · 安全的染黑：而 2→5、4→5（高亮）只通向终点 5（黑/安全），6 本身是终点：它们的出边都不踩灰 → 染黑（安全）。结论和反图拓扑完全一致：[2,4,5,6]。

例二 · 一条没有环的图：换个图练手：1 指向所有点，但整张图没有任何环。先数出度——0 和 4 出度为 0，是终点。

例二 · 0、4 先安全：0、4 确认安全（绿）。沿反图回传：4 通知前驱 3（边 3→4 高亮），out[3] 削到 0 → 3 入队。1 也被削但还剩 3 条边。

例二 · 3、2 接力归零：3 确认安全（绿），通知它唯一前驱 2（边 2→3 高亮），out[2] 归 0 → 2 入队。链条像推骨牌一样一节节往回认。

例二收工 · 全部安全：2 安全后再削 1，out[1] 终于归 0，1 也安全。没有环的图，所有点最终都安全 → [0,1,2,3,4]。对照例一：环是唯一让点不安全的原因。

套路模板：记住这个变形：普通拓扑排序削入度，本题削出度、并且要反着建图来回传消息。

边界三连：无出边的点必安全；自环、任何环上的点都不安全。环是不安全的唯一来源。

面试追问：面试常问 为何要记忆化 以及 三色 vs 反图拓扑 两种写法的取舍。