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;
    }
};