LeetCode 802. 找到最终的安全状态
题目描述
题意分析
没有出边的节点是终端节点。从某个节点出发，无论怎样选择后续边，最终都会停在终端节点，它才是安全节点。只要能够进入环，就可以沿环一直行走，因此该节点不安全。
需要按编号升序返回所有安全节点。关键是“所有路径”都终止，不能只找到一条通往终端的路径就判定安全。
解法：反图上的出度消除
核心思路
[!blue]
终端节点天然安全。进一步，如果一个节点的所有直接后继都已安全，那么无论下一步走向哪个后继，之后都能终止，这个节点也安全。因此可以从原图出度为零的节点开始，向前驱逐步传播安全性。
建立反图
reverse[v]，保存所有能一步走到v的前驱，同时令degree[u]记录原图节点u的出度。初始将全部出度为零的节点入队。每次取出安全节点
v，相当于把它从待处理图中消除。对每个前驱u，将degree[u]减一，表示边u→v已经不需要继续保留。某个前驱的剩余出度降为零时，它的所有后继都已被安全消除，因此也可以确认安全并入队。这一过程既不会误收，也不会漏收。入队节点的所有后继都已经安全，所以归纳可知每个被消除节点都安全。队列耗尽后，若某节点仍有正的剩余出度，它就还有一条边走向未消除节点；沿剩余边不断前进，在有限节点中必然重复到达某个节点，形成一个可达环。因此所有未被消除的节点都不安全。
处理完成后，剩余出度为零的节点正好就是全部安全节点。队列的处理顺序不保证编号递增，所以最后再按编号从小到大扫描，将出度为零的节点加入答案即可。
解题步骤
- 对每条原图边
u→v，将u加入reverse[v]，并记录每个节点的原始出度。- 将所有出度为零的终端节点放入队列。
- 取出节点
v，遍历它在反图中的前驱，将这些前驱的剩余出度各减一。- 前驱出度刚好降为零时入队，继续向它的前驱传播。
- 队列为空后按节点编号扫描，收集最终出度为零的节点。若初始没有终端节点，队列为空，所有节点都会留在包含可达环的部分中。
代码实现
class Solution {
public List<Integer> eventualSafeNodes(int[][] graph) {
int n = graph.length;
List<List<Integer>> reverse = new ArrayList<>();
int[] degree = new int[n];
for (int i = 0; i < n; i++) {
reverse.add(new ArrayList<>());
}
for (int u = 0; u < n; u++) {
degree[u] = graph[u].length;
for (int v : graph[u]) {
reverse.get(v).add(u);
}
}
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (degree[i] == 0) {
queue.add(i);
}
}
while (!queue.isEmpty()) {
int v = queue.remove();
for (int u : reverse.get(v)) {
if (--degree[u] == 0) {
queue.add(u);
}
}
}
List<Integer> answer = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (degree[i] == 0) {
answer.add(i);
}
}
return answer;
}
}
func eventualSafeNodes(graph [][]int) []int {
n := len(graph)
reverse := make([][]int, n)
degree := make([]int, n)
for u, neighbors := range graph {
degree[u] = len(neighbors)
for _, v := range neighbors {
reverse[v] = append(reverse[v], u)
}
}
queue := []int{}
for i := range graph {
if degree[i] == 0 {
queue = append(queue, i)
}
}
for head := 0; head < len(queue); head++ {
for _, u := range reverse[queue[head]] {
degree[u]--
if degree[u] == 0 {
queue = append(queue, u)
}
}
}
answer := []int{}
for i := range graph {
if degree[i] == 0 {
answer = append(answer, i)
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(V+E)$。建图和最后扫描各为线性，每个节点最多入队一次，每条反向边也只在其对应后继出队时处理一次。
- 空间复杂度：$O(V+E)$。反图保存全部节点和边，度数数组、队列与答案均为 $O(V)$。
关键点总结
[!green]
- 所有后继安全，当前节点才安全，对应剩余出度必须降为零。
- 反图用来找到安全节点的前驱，度数记录的始终是原图出度的剩余量。
- 未消除部分每个节点都有剩余出边，沿边前进必能到达环，说明保留下来的恰好是不安全节点。
- 最后按编号扫描就能满足升序要求，无需依赖队列顺序或另行排序。
易错点总结
[!yellow]
- 只要一个后继安全就把当前节点判为安全，会漏掉其他后继能进入环的情况。
- 从原图入度为零的节点开始消除，处理的是前置依赖，无法表达本题所有后续路径都会结束的条件。
- 只判断节点自己是否在环上，会遗漏能够走到环、但不属于环的节点。
- 图允许自环，自环节点至少保留一条指向自己的出边，不会变成安全节点。
- 按出队顺序直接输出，可能违反结果按编号升序排列的要求。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 207. 课程表 | 中等 | 同样使用度数归零的拓扑消除，课程表从入度 0 开始，本题从原图出度 0 开始。 |
| 210. 课程表 II | 中等 | 对照拓扑过程中队列顺序与答案顺序；本题需要最终按节点编号输出。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！