LeetCode 802.找到最终的安全状态_leetcode802找到最终安全的状态

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

在有向图中, 我们从某个节点和每个转向处开始, 沿着图的有向边走。 如果我们到达的节点是终点 (即它没有连出的有向边), 我们停止。

现在, 如果我们最后能走到终点，那么我们的起始节点是最终安全的。 更具体地说, 存在一个自然数 K,  无论选择从哪里开始行走, 我们走了不到 K 步后必能停止在一个终点。

哪些节点最终是安全的？ 结果返回一个有序的数组。

该有向图有 N 个节点，标签为 0, 1, ..., N-1, 其中 N 是 graph 的节点数.  图以以下的形式给出: graph[i] 是节点 j 的一个列表，满足 (i, j) 是图的一条有向边。

示例：
输入：graph = [[1,2],[2,3],[5],[0],[5],[],[]]
输出：[2,4,5,6]
这里是上图的示意图。

1
2
3
4
5
6
7
8
9
10
11
12
13

看起来很乱，其实要求就是无论选择从哪里开始行走最终都能走到终点

平时都是任意有一条能到达就行，这题是要求所有的边都能到达，挺新鲜

样例中的0->1,1->3,3->1这样形成的循环，走不到终点，所以这道题就是判断每个点的所有情况能不能都走到终点

用vis数组判断是否被访问过，safe数组判断该结点是否为安全节点

class Solution
{
  private:
    static const int maxn = 32005;
    bool vis[maxn], safe[maxn];
    bool dfs(int cur, vector<vector<int>> &graph)
    {
    	//先判断是否为安全节点，因为是深度优先，所以可能会
    	//后访问到一个安全结点，而该结点先前一定被访问过了
    	//比如把样例改成[[1,2],[2,3],[5],[6],[5],[],[]]
    	//不先判断安全的话0结点不会加入答案
        if (safe[cur])
            return true;
        //不安全并且访问过，那一定是不可以的
        if (vis[cur])
            return false;
        vis[cur] = true;
        
        if (graph[cur].size() == 0)//终点，设为安全
        {
            safe[cur] = true;
            return true;
        }
        
        for (int i = 0; i < graph[cur].size(); ++i)
            if (!dfs(graph[cur][i], graph))//任意一边不满足返回假
                return false;
        safe[cur] = true;//记得把当前结点设为安全
        return true;
    }

  public:
    vector<int> eventualSafeNodes(vector<vector<int>> &graph)
    {
        vector<int> ans;
        memset(safe, 0, sizeof(safe));
		
        for (int i = 0; i < graph.size(); ++i)
        {
            memset(vis, 0, sizeof(vis));
            if (dfs(i, graph))
                ans.push_back(i);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46