[leetcode] 802. Find Eventual Safe States

Description

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

Now, say our starting node is eventually safe if and only if we must eventually walk to a terminal node. More specifically, there exists a natural number K so that for any choice of where to walk, we must have stopped at a terminal node in less than K steps.

Which nodes are eventually safe? Return them as an array in sorted order.

The directed graph has N nodes with labels 0, 1, …, 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.

Example:
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Here is a diagram of the above graph.

Note:

• graph will have length at most 10000.
• The number of edges in the graph will not exceed 32000.
• Each graph[i] will be a sorted list of different integers, chosen within the range [0, graph.length - 1].

分析

题目的意思是：给你一个图，和一些转移状态，判断哪些结点安全，安全结点定义为起始结点，终点。

• 初始化为0号色，然后dfs时将起始点染1号色（成环的点），安全点染2号色。
• 本质的解法是dfs，如果结点构成环，则不能加入结果集合，如果不构成环，则加入结果集合。

代码

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n=graph.size();
        vector<int> colors(n,0);
        vector<int> res;
        for(int i=0;i<n;i++){   //dfs每个结点判断是否有环
            if(solve(graph,colors,i)){  //从i出发有环则返回false
                res.push_back(i);
            }
        }
        return res;
    }
    bool solve(vector<vector<int>>& graph,vector<int>& colors,int node){
        if(colors[node]>0){
            return colors[node]==2;  //如果染色是安全状态2就返回true
        }
        colors[node]=1; //初始染1号色，相当于标记这次dfs过程中访问过它，但它的状态不确定是否安全
        for(int i:graph[node]){ //如果它的邻接点或者他的邻接点的邻接点dfs时又访问了i结点那么就说明成环了。
            if(colors[i]==2) continue;
            if(colors[i]==1||!solve(graph,colors,i)){
                return false;
            }
        }
        colors[node]=2;
        return true;
    }
};

参考文献

802. Find Eventual Safe States
leetcode802——Find Eventual Safe States