Leetcode---802. 找到最終的安全狀态---基于Tarjin的解法

802. 找到最終的安全狀态

在有向圖中，以某個節點為起始節點，從該點出發，每一步沿着圖中的一條有向邊行走。如果到達的節點是終點（即它沒有連出的有向邊），則停止。

對于一個起始節點，如果從該節點出發，無論每一步選擇沿哪條有向邊行走，最後必然在有限步内到達終點，則将該起始節點稱作是 安全 的。

傳回一個由圖中所有安全的起始節點組成的數組作為答案。答案數組中的元素應當按 升序 排列。

該有向圖有

n

個節點，按

到

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 <= 104

• 0 <= graph[i].length <= n

• graph[i]

  按嚴格遞增順序排列。
• 圖中可能包含自環。
• 圖中邊的數目在範圍

  [1, 4 * 104]

  内。

Code

class Solution {
public:
    stack<int> stk;
    vector<int> ans;
    int cnt = 0;

    void tarjin(int x, vector<int>& low, vector<int>& dfn, vector<vector<int>>& graph, vector<bool>& vis) {
        if (low[x] == -1) return;
        low[x] = dfn[x] = ++cnt;
        vis[x] = true;
        stk.push(x);
		// 存在自環，或者到達的點存在環都直接傳回
        for (int i = 0; i < graph[x].size(); i++) {
            if (graph[x][i] == x || low[graph[x][i]] == -1) {
                stk.pop();
                low[x] = -1;
                vis[x] = false;
                return;
            }
        }

        for (int i = 0; i < graph[x].size(); i++) {
            if (!dfn[graph[x][i]]) {
                tarjin(graph[x][i], low, dfn, graph, vis);
                low[x] = min(low[x], low[graph[x][i]]);
            }
            else if (vis[graph[x][i]]) {
                low[x] = min(low[x], dfn[graph[x][i]]);
            }
        }

        if (dfn[x] == low[x]) {
        	// 如果沒有環
            if (stk.top() == x) {
                ans.push_back(x);
            }
            // 存在環，修改标記
            else {
                while (stk.top() != x) {
                    vis[stk.top()] = false;
                    low[stk.top()] = -1;
                    stk.pop();
                }
                low[x] = -1;
            }
            vis[x] = false;
            stk.pop();
        }
    }

    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> low(n, 0);
        vector<int> dfn(n, 0);
        vector<bool> vis(n, false);

        for (int i = 0; i < n; i++) {
            if (!dfn[i]) tarjin(i, low, dfn, graph, vis);
        }
        sort(ans.begin(), ans.end());
        return ans;
    }
};