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

题目描述

这是 LeetCode 上的 802. 找到最终的安全状态 ，难度为中等。

在有向图中，以某个节点为起始节点，从该点出发，每一步沿着图中的一条有向边行走。如果到达的节点是终点（即它没有连出的有向边），则停止。

对于一个起始节点，如果从该节点出发，无论每一步选择沿哪条有向边行走，最后必然在有限步内到达终点，则将该起始节点称作是安全的。

返回一个由图中所有安全的起始节点组成的数组作为答案。答案数组中的元素应当按升序排列。

该有向图有 n 个节点，按 0 到 n - 1 编号，其中 n 是 graph 的节点数。图以下述形式给出：graph[i] 是编号 j 节点的一个列表，满足 (i, j) 是图的一条有向边。

示例 1：

输入：graph = [[1,2],[2,3],[5],[0],[5],[],[]]

输出：[2,4,5,6]

解释：示意图如上。

示例 2：

1
2
3

输入：graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]

输出：[4]

提示：

n == graph.length
1 <= n <= $10^4$
0 <= graph[i].length <= n
graph[i] 按严格递增顺序排列。
图中可能包含自环。
图中边的数目在范围 [1, 4 * $10^4$] 内。

基本分析 & 拓扑排序

为了方便，我们令点数为 $n$，边数为 $m$。

在图论中，一个有向无环图必然存在至少一个拓扑序与之对应，反之亦然。

如果对拓扑排序不熟悉的小伙伴，可以看看拓扑排序。

简单来说，就是将图中的所有节点展开成一维序列，对于序列中任意的节点 $(u, v)$，如果在序列中 $u$ 在 $v$ 的前面，则说明在图中存在从 $u$ 出发达到 $v$ 的通路，即 $u$ 排在 $v$ 的前面。反之亦然。

同时，我们需要知晓「入度」和「出度」的概念：

入度：有多少条边直接指向该节点；
出度：由该节点指出边的有多少条。

因此，对于有向图的拓扑排序，我们可以使用如下思路输出拓扑序（BFS 方式）：

起始时，将所有入度为 $0$ 的节点进行入队（入度为 $0$，说明没有边指向这些节点，将它们放到拓扑排序的首部，不会违反拓扑序定义）；
从队列中进行节点出队操作，出队序列就是对应我们输出的拓扑序。
对于当前弹出的节点 $x$，遍历 $x$ 的所有出度，即遍历所有由 $x$ 直接指向的节点 $y$，对 $y$ 做入度减一操作（因为 $x$ 节点已经从队列中弹出，被添加到拓扑序中，等价于从 $x$ 节点从有向图中被移除，相应的由 $x$ 发出的边也应当被删除，带来的影响是与 $x$ 相连的节点 $y$ 的入度减一）；
对 $y$ 进行入度减一之后，检查 $y$ 的入度是否为 $0$，如果为 $0$ 则将 $y$ 入队（当 $y$ 的入度为 $0$，说明有向图中在 $y$ 前面的所有的节点均被添加到拓扑序中，此时 $y$ 可以作为拓扑序的某个片段的首部被添加，而不是违反拓扑序的定义）；
循环流程 $2$、$3$ 直到队列为空。

证明

上述 BFS 方法能够求得「某个有向无环图的拓扑序」的前提是：我们必然能够找到（至少）一个「入度为 $0$ 的点」，在起始时将其入队。

这可以使用反证法进行证明：假设有向无环图的拓扑序不存在入度为 $0$ 的点。

那么从图中的任意节点 $x$ 进行出发，沿着边进行反向检索，由于不存在入度为 $0$ 的节点，因此每个点都能够找到上一个节点。

当我们找到一条长度为 $n + 1$ 的反向路径时，由于我们图中只有 $n$ 个节点，因此必然有至少一个节点在该路径中重复出现，即该反向路径中存在环，与我们「有向无环图」的起始条件冲突。

得证「有向无环图的拓扑序」必然存在（至少）一个「入度为 $0$ 的点」。

即按照上述的 BFS 方法，我们能够按照流程迭代下去，直到将有向无环图的所有节点从队列中弹出。

反之，如果一个图不是「有向无环图」的话，我们是无法将所有节点入队的，因此能够通过入队节点数量是否为 $n$ 来判断是否为有向无环图。

反向图 + 拓扑排序

回到本题，根据题目对「安全节点」的定义，我们知道如果一个节点无法进入「环」的话则是安全的，否则是不安全的。

另外我们发现，如果想要判断某个节点数 $x$ 是否安全，起始时将 $x$ 进行入队，并跑一遍拓扑排序是不足够的。

因为我们无法事先确保 $x$ 满足入度为 $0$ 的要求，所以当我们处理到与 $x$ 相连的节点 $y$ 时，可能会存在 $y$ 节点入度无法减到 $0$ 的情况，即我们无法输出真实拓扑序中，从 $x$ 节点开始到结尾的完整部分。

但是根据我们「证明」部分的启发，我们可以将所有边进行反向，这时候「入度」和「出度」翻转了。

对于那些反向图中「入度」为 $0$ 的点集 $x$，其实就是原图中「出度」为 $0$ 的节点，它们「出度」为 $0$，根本没指向任何节点，必然无法进入环，是安全的；同时由它们在反向图中指向的节点（在原图中只指向它们的节点），必然也是无法进入环的，对应到反向图中，就是那些减去 $x$ 对应的入度之后，入度为 $0$ 的节点。

因此整个过程就是将图进行反向，再跑一遍拓扑排序，如果某个节点出现在拓扑序列，说明其进入过队列，说明其入度为 $0$，其是安全的，其余节点则是在环内非安全节点。

另外，这里的存图方式还是使用前几天一直使用的「链式前向星」，关于几个数组的定义以及其他的存图方式，如果还是有不熟悉的小伙伴可以在这里查阅，本次不再赘述。

代码：

class Solution {
    int N = (int)1e4+10, M = 4 * N;
    int idx;
    int[] he = new int[N], e = new int[M], ne = new int[M];
    int[] cnts = new int[N];
    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx++;
    }
    public List<Integer> eventualSafeNodes(int[][] g) {
        int n = g.length;
        // 存反向图，并统计入度
        Arrays.fill(he, -1);
        for (int i = 0; i < n; i++) {
            for (int j : g[i]) {
                add(j, i);
                cnts[i]++;
            }
        }
        // BFS 求反向图拓扑排序
        Deque<Integer> d = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (cnts[i] == 0) d.addLast(i);
        }
        while (!d.isEmpty()) {
            int poll = d.pollFirst();
            for (int i = he[poll]; i != -1; i = ne[i]) {
                int j = e[i];
                if (--cnts[j] == 0) d.addLast(j);
            }
        }
        // 遍历答案：如果某个节点出现在拓扑序列，说明其进入过队列，说明其入度为 0
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (cnts[i] == 0) ans.add(i);
        }
        return ans;
    }
}

时间复杂度：$O(n + m)$
空间复杂度：$O(n + m)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.802 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

图拓扑排序

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 847. 访问所有节点的最短路径上一篇

LC 611. 有效三角形的个数下一篇