题目描述
这是 LeetCode 上的 802. 找到最终的安全状态 ，难度为 中等。
Tag : 「图」、「拓扑排序」
在有向图中，以某个节点为起始节点，从该点出发，每一步沿着图中的一条有向边行走。
如果到达的节点是终点（即它没有连出的有向边），则停止。
对于一个起始节点，如果从该节点出发，无论每一步选择沿哪条有向边行走，最后必然在有限步内到达终点，则将该起始节点称作是 安全 的。
返回一个由图中所有安全的起始节点组成的数组作为答案。答案数组中的元素应当按 升序 排列。
该有向图有 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：
输入：graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]] 输出：[4] 复制代码
提示：
- n == graph.length
- 1 <= n <= 10^4104
- 0 <= graph[i].length <= n
- graph[i] 按严格递增顺序排列。
- 图中可能包含自环。
- 图中边的数目在范围 [1, 4 * 10^4104] 内。
基本分析 & 拓扑排序
为了方便，我们令点数为 nn，边数为 mm。
在图论中，一个有向无环图必然存在至少一个拓扑序与之对应，反之亦然。
如果对拓扑排序不熟悉的小伙伴，可以看看 拓扑排序。
简单来说，就是将图中的所有节点展开成一维序列，对于序列中任意的节点 (u, v)(u,v)，如果在序列中 uu 在 vv 的前面，则说明在图中存在从 uu 出发达到 vv 的通路，即 uu 排在 vv 的前面。反之亦然。
同时，我们需要知晓「入度」和「出度」的概念：
- 入度：有多少条边直接指向该节点；
- 出度：由该节点指出边的有多少条。
因此，对于有向图的拓扑排序，我们可以使用如下思路输出拓扑序（BFS 方式）：
- 起始时，将所有入度为 00 的节点进行入队（入度为 00，说明没有边指向这些节点，将它们放到拓扑排序的首部，不会违反拓扑序定义）；
- 从队列中进行节点出队操作，出队序列就是对应我们输出的拓扑序。 对于当前弹出的节点 xx，遍历 xx 的所有出度，即遍历所有由 xx 直接指向的节点 yy，对 yy 做入度减一操作（因为 xx 节点已经从队列中弹出，被添加到拓扑序中，等价于从 xx 节点从有向图中被移除，相应的由 xx 发出的边也应当被删除，带来的影响是与 xx 相连的节点 yy 的入度减一）；
- 对 yy 进行入度减一之后，检查 yy 的入度是否为 00，如果为 00 则将 yy 入队（当 yy 的入度为 00，说明有向图中在 yy 前面的所有的节点均被添加到拓扑序中，此时 yy 可以作为拓扑序的某个片段的首部被添加，而不是违反拓扑序的定义）；
- 循环流程 22、33 直到队列为空。
证明
上述 BFS 方法能够求得「某个有向无环图的拓扑序」的前提是：我们必然能够找到（至少）一个「入度为 00 的点」，在起始时将其入队。
这可以使用反证法进行证明：假设有向无环图的拓扑序不存在入度为 00 的点。
那么从图中的任意节点 xx 进行出发，沿着边进行反向检索，由于不存在入度为 00 的节点，因此每个点都能够找到上一个节点。
当我们找到一条长度为 n + 1n+1 的反向路径时，由于我们图中只有 nn 个节点，因此必然有至少一个节点在该路径中重复出现，即该反向路径中存在环，与我们「有向无环图」的起始条件冲突。
得证「有向无环图的拓扑序」必然存在（至少）一个「入度为 00 的点」。
即按照上述的 BFS 方法，我们能够按照流程迭代下去，直到将有向无环图的所有节点从队列中弹出。
反之，如果一个图不是「有向无环图」的话，我们是无法将所有节点入队的，因此能够通过入队节点数量是否为 nn 来判断是否为有向无环图。
反向图 + 拓扑排序
回到本题，根据题目对「安全节点」的定义，我们知道如果一个节点无法进入「环」的话则是安全的，否则是不安全的。
另外我们发现，如果想要判断某个节点数 xx 是否安全，起始时将 xx 进行入队，并跑一遍拓扑排序是不足够的。
因为我们无法事先确保 xx 满足入度为 00 的要求，所以当我们处理到与 xx 相连的节点 yy 时，可能会存在 yy 节点入度无法减到 00 的情况，即我们无法输出真实拓扑序中，从 xx 节点开始到结尾的完整部分。
但是根据我们「证明」部分的启发，我们可以将所有边进行反向，这时候「入度」和「出度」翻转了。
对于那些反向图中「入度」为 00 的点集 xx，其实就是原图中「出度」为 00 的节点，它们「出度」为 00，根本没指向任何节点，必然无法进入环，是安全的；同时由它们在反向图中指向的节点（在原图中只指向它们的节点），必然也是无法进入环的，对应到反向图中，就是那些减去 xx 对应的入度之后，入度为 00 的节点。
因此整个过程就是将图进行反向，再跑一遍拓扑排序，如果某个节点出现在拓扑序列，说明其进入过队列，说明其入度为 00，其是安全的，其余节点则是在环内非安全节点。
另外，这里的存图方式还是使用前几天一直使用的「链式前向星」，关于几个数组的定义以及其他的存图方式，如果还是有不熟悉的小伙伴可以在 这里 查阅，本次不再赘述。
代码：
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)
- 空间复杂度：O(n + m)O(n+m)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.802 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
