[LeetCode] 802. Find Eventual Safe States

[grandyang]

 

We start at some node in a directed graph, and every turn, we walk along a directed edge of the graph. If we reach a terminal node (that is, it has no outgoing directed edges), we stop.

We define a starting node to be safe if we must eventually walk to a terminal node. More specifically, there is a natural number k, so that we must have stopped at a terminal node in less than k steps for any choice of where to walk.

Return  an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.

The directed graph has n nodes with labels from 0 to n - 1, where n is the length of graph. The graph is given in the following form: graph[i] is a list of labels j such that (i, j) is a directed edge of the graph, going from node i to node j.

 

Example 1:

Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Explanation: The given graph is shown above.

Example 2:

Input: graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
Output: [4]

 

Constraints:

• n == graph.length
• 1 <= n <= 104
• 0 <= graph[i].legnth <= n
• graph[i] is sorted in a strictly increasing order.
• The graph may contain self-loops.
• The number of edges in the graph will be in the range [1, 4 * 104].

 

这道题给了我们一个有向图，然后定义了一种最终安全状态的结点，就是说该结点要在自然数K步内停止，所谓停止的意思，就是再没有向外的边，即没有出度，像上面例子中的结点5和6就是出度为0，因为 graph[5] 和 graph[6] 均为空。那么分析题目中的例子，除了没有出度的结点5和6之外，结点2和4也是安全状态结点，为啥呢，可以发现结点2和4都只能到达结点5，而结点5本身就是安全状态点，所以2和4也就是安全状态点了，可以得出的结论是，若某结点唯一能到达的结点是安全状态结点的话，那么该结点也同样是安全状态结点。这样就可以从没有出度的安全状态往回推，比如结点5，往回推可以到达结点4和2，先看结点4，此时先回推到结点4，然后将这条边断开，那么此时结点4出度为0，则标记结点4也为安全状态结点，同理，回推到结点2，断开边，此时结点2虽然入度仍为2，但是出度为0了，标记结点2也为安全状态结点。

分析到这里，思路应该比较明朗了，由于需要回推边，所以需要建立逆向边，用一个集合数组来存，由于题目要求返回的结点有序，可以利用集合 TreeSet 的自动排序的特性，由于需要断开边，为了不修改输入数据，所以干脆再建一个顺向边得了，即跟输入数据相同。还需要一个 safe 数组，布尔型的，来标记哪些结点是安全状态结点。在遍历结点的时候，直接先将出度为0的安全状态结点找出来，排入一个队列 queue 中，方便后续的处理。后续的处理就有些类似 BFS 的操作了，循环非空 queue，取出队首元素，标记 safe 中该结点为安全状态结点，然后遍历其逆向边的结点，即可以到达当前队首结点的所有结点，在正向边集合中删除对应的边，如果此时结点出度为0了，将其加入队列 queue 中等待下一步处理，这样 while 循环退出后，所有的安全状态结点都已经标记好了，直接遍历 safe 数组，将其存入结果 res 中即可，参见代码如下：

 

解法一：

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        vector<int> res;
        int n = graph.size();
        vector<bool> safe(n, false);
        vector<set<int>> g(n, set<int>()), revg = g;
        queue<int> q;
        for (int i = 0; i < n; ++i) {
            if (graph[i].empty()) q.push(i);
            for (int j : graph[i]) {
                g[i].insert(j);
                revg[j].insert(i);
            }
        }
        while (!q.empty()) {
            auto t = q.front(); q.pop();
            safe[t] = true;
            for (int i : revg[t]) {
                g[i].erase(t);
                if (g[i].empty()) q.push(i);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (safe[i]) res.push_back(i);
        }
        return res;
    }
};

 

我们再来看一种 DFS 遍历有向图的解法。仔细分析题目中的例子，不难发现，之所以某些结点不是安全状态，因为有环的存在，而环经过的所有结点，一定不是安全状态结点，还有就是如果有结点可以到达环上的任意一个结点，那么该结点也不是安全的，所以可以通过 DFS 遍历有向图来找出环即可。在大多数的算法中，经典的 DFS 遍历法对于结点都有三种状态标记，white，gray，和 black，其中 white 表示结点还未遍历，gray 表示正在遍历邻结点，black 表示已经结束该结点的遍历。那么可以对每个结点都调用递归函数，在递归函数中，如果当前结点不是 white，表示该结点已经访问过了，那么如果当前结点是 black，直接返回 true，如果是 gray，直接返回 false，因为遇到 gray 的结点，表示一定有环存在。否则我们给结点标记 gray，然后开始遍历所有邻接结点，如果某个邻结点是 black，直接跳过该结点。如果某个邻结点是 gray，或者对该邻结点调用递归返回 false了，说明当前结点是环结点或者该结点可以到达环上的结点，不是安全状态，返回 false。如果循环结束了，当前结点标记为 black，并且返回 true，参见代码如下：

 

解法二：

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> res, color(n); // 0 white, 1 gray, 2 black
        for (int i = 0; i < n; ++i) {
            if (helper(graph, i, color)) res.push_back(i);
        }
        return res;
    }
    bool helper(vector<vector<int>>& graph, int cur, vector<int>& color) {
        if (color[cur] > 0) return color[cur] == 2;
        color[cur] = 1;
        for (int i : graph[cur]) {
            if (color[i] == 2) continue;
            if (color[i] == 1 || !helper(graph, i, color)) {
                return false;
            }
        }
        color[cur] = 2;
        return true;
    }
};

 

Github 同步地址：

#802

 

参考资料：

https://leetcode.com/problems/find-eventual-safe-states/

https://leetcode.com/problems/find-eventual-safe-states/discuss/119871/Straightforward-Java-solution-easy-to-understand!

 

LeetCode All in One 题目讲解汇总(持续更新中...)