在有向图中, 我们从某个节点和每个转向处开始, 沿着图的有向边走。 如果我们到达的节点是终点 (即它没有连出的有向边), 我们停止。
现在, 如果我们最后能走到终点，那么我们的起始节点是最终安全的。 更具体地说, 存在一个自然数 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] 这里是上图的示意图。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-eventual-safe-states 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：这道题的实质是利用DFS找环路，只要从当前节点出发找到了环路，那么这个节点就不符合要求，所以我们需要引入一个DFS 以及表示当前节点访问状态的数组，对每一个节点进行DFS，知道找到出度为0的节点。
class Solution { public: //主要是判断有无环路就可以了 vector<int> eventualSafeNodes(vector<vector<int>>& graph) { vector<int> results; vector<int> color(graph.size(),0); for(int i = 0;i<graph.size();i++) { if(DFS(i, color, graph)) results.push_back(i); } return results; } bool DFS(int& node, vector<int>& color,vector<vector<int>>& graph) { //0 表示未访问 1表示在当前这一轮中被访问并在环中 2表示已经访问完毕且不在环中 if(color[node] > 0)//如果大于0 return color[node] == 2;//判断是否是无环的 color[node] = 1;//表示当前访问 for(int neighbour: graph[node]) { if(color[neighbour] == 2)//如果该节点已经被访问过 continue; if(color[neighbour] == 1||!DFS(neighbour,color,graph)) return false; } color[node] = 2;//否则 表示当前节点并无问题 return true; } };