題目描述
這是 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 <=
- 0 <= graph[i].length <= n
- graph[i] 按嚴格遞增順序排列。
- 圖中可能包含自環。
- 圖中邊的數目在範圍 [1, 4 *] 内。
基本分析 & 拓撲排序
為了友善，我們令點數為 ，邊數為 。
在圖論中，一個有向無環圖必然存在至少一個拓撲序與之對應，反之亦然。
如果對拓撲排序不熟悉的小夥伴，可以看看 拓撲排序。
簡單來說，就是将圖中的所有節點展開成一維序列，對于序列中任意的節點 ，如果在序列中 在 的前面，則說明在圖中存在從 出發達到 的通路，即 排在 的前面。反之亦然。
同時，我們需要知曉「入度」和「出度」的概念：
- 入度：有多少條邊直接指向該節點；
- 出度：由該節點指出邊的有多少條。
是以，對于有向圖的拓撲排序，我們可以使用如下思路輸出拓撲序（
BFS
方式）：
- 起始時，将所有入度為的節點進行入隊（入度為，說明沒有邊指向這些節點，将它們放到拓撲排序的首部，不會違反拓撲序定義）；
-
從隊列中進行節點出隊操作，出隊序列就是對應我們輸出的拓撲序。
對于目前彈出的節點，周遊的所有出度，即周遊所有由直接指向的節點，對做入度減一操作（因為節點已經從隊列中彈出，被添加到拓撲序中，等價于從節點從有向圖中被移除，相應的由發出的邊也應當被删除，帶來的影響是與相連的節點的入度減一）；
- 對進行入度減一之後，檢查的入度是否為，如果為則将入隊（當的入度為，說明有向圖中在前面的所有的節點均被添加到拓撲序中，此時可以作為拓撲序的某個片段的首部被添加，而不是違反拓撲序的定義）；
- 循環流程、直到隊列為空。
證明
上述
BFS
方法能夠求得「某個有向無環圖的拓撲序」的前提是：我們必然能夠找到（至少）一個「入度為 的點」，在起始時将其入隊。
這可以使用反證法進行證明：假設有向無環圖的拓撲序不存在入度為 的點。
那麼從圖中的任意節點 進行出發，沿着邊進行反向檢索，由于不存在入度為 的節點，是以每個點都能夠找到上一個節點。
當我們找到一條長度為 的反向路徑時，由于我們圖中隻有 個節點，是以必然有至少一個節點在該路徑中重複出現，即該反向路徑中存在環，與我們「有向無環圖」的起始條件沖突。
得證「有向無環圖的拓撲序」必然存在（至少）一個「入度為 的點」。
即按照上述的
BFS
方法，我們能夠按照流程疊代下去，直到将有向無環圖的所有節點從隊列中彈出。
反之，如果一個圖不是「有向無環圖」的話，我們是無法将所有節點入隊的，是以能夠通過入隊節點數量是否為 來判斷是否為有向無環圖。
反向圖 + 拓撲排序
回到本題，根據題目對「安全節點」的定義，我們知道如果一個節點無法進入「環」的話則是安全的，否則是不安全的。
另外我們發現，如果想要判斷某個節點數 是否安全，起始時将 進行入隊，并跑一遍拓撲排序是不足夠的。
因為我們無法事先確定 滿足入度為 的要求，是以當我們處理到與 相連的節點 時，可能會存在 節點入度無法減到 的情況，即我們無法輸出真實拓撲序中，從 節點開始到結尾的完整部分。
但是根據我們「證明」部分的啟發，我們可以将所有邊進行反向，這時候「入度」和「出度」翻轉了。
對于那些反向圖中「入度」為 的點集 ，其實就是原圖中「出度」為 的節點，它們「出度」為 ，根本沒指向任何節點，必然無法進入環，是安全的；同時由它們在反向圖中指向的節點（在原圖中隻指向它們的節點），必然也是無法進入環的，對應到反向圖中，就是那些減去 對應的入度之後，入度為 的節點。
是以整個過程就是将圖進行反向，再跑一遍拓撲排序，如果某個節點出現在拓撲序列，說明其進入過隊列，說明其入度為 ，其是安全的，其餘節點則是在環内非安全節點。
另外，這裡的存圖方式還是使用前幾天一直使用的「鍊式前向星」，關于幾個數組的定義以及其他的存圖方式，如果還是有不熟悉的小夥伴可以在 這裡 查閱，本次不再贅述。
代碼：
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;
}
} - 時間複雜度：
- 空間複雜度：
最後
這是我們「刷穿 LeetCode」系列文章的第
No.802
篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。