题目
在有向图中，以某个节点为起始节点，从该点出发，每一步沿着图中的一条有向边行走。如果到达的节点是终点（即它没有连出的有向边），则停止。
对于一个起始节点，如果从该节点出发，无论每一步选择沿哪条有向边行走，最后必然在有限步内到达终点，则将该起始节点称作是 安全 的。
返回一个由图中所有安全的起始节点组成的数组作为答案。答案数组中的元素应当按 升序 排列。
该有向图有 n 个节点，按 0 到 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]
解题
方法一：拓扑排序
若一个节点的出边相连的点都是安全的，则该点也是安全的，在反向图中，inDeg就是记录出边数量，每次从安全点遍历到该点，都会使得inDeg-1，当inDeg==0，代表每个节点出边相连的点都是安全的。
graph[x].size()是正向图的出度，也就是反向图的入度
class Solution { public: vector<int> eventualSafeNodes(vector<vector<int>>& graph) { int n=graph.size(); //获得反向图和每个顶点的入度 vector<vector<int>> rg(n);//reversed graph vector<int> inDeg(n); for(int x=0;x<n;x++){ for(int y:graph[x]){ rg[y].push_back(x); } inDeg[x]=graph[x].size();//反向图的入度是正向图的出度 } //初始化（将 入度为0的顶点，加入队列） queue<int> q; for(int i=0;i<n;i++){ if(inDeg[i]==0) q.push(i); } //将入度为0的顶点的相邻边删去，相邻顶点入度-1，如果入度为0，加入到队列中 while(!q.empty()){ int y=q.front(); q.pop(); for(int x:rg[y]){ if(--inDeg[x]==0){ q.push(x); } } } //入度为0的顶点 即为安全点 vector<int> res; for(int i=0;i<n;i++){ if(inDeg[i]==0) res.push_back(i); } return res; } };
方法二：深度优先搜索 + 三色标记法
解答
由于color[x]=1后面遍历每个出边，如果出边对应顶点都是安全点，那么color[x]=2,如果不安全则为color[x]=1。
因此当再次遍历到的时候，访问过的话color[x]>0。出边的顶点是不安全的，那么该顶点一定是不安全的，出边的顶点是安全的，那么该顶点是安全的。
写法一：
由于用到多次传参，比如graph和color,可以使用function包装lambda表达式，减少代码量
class Solution { public: vector<int> eventualSafeNodes(vector<vector<int>> &graph) { int n = graph.size(); vector<int> color(n); function<bool(int)> safe = [&](int x) { if (color[x] > 0) { return color[x] == 2;//如果该顶点是安全点，就返回true } color[x] = 1; for (int y : graph[x]) {//任意的出边都要是安全点才行，否则该顶点就不是安全顶点 if (!safe(y)) { return false; } } color[x] = 2;//任意出边都是安全点，因此该顶点是安全点 return true; }; vector<int> ans; for (int i = 0; i < n; ++i) { if (safe(i)) { ans.push_back(i); } } return ans; } };
补充
function在这当作lambda表达式的装饰器，统一成function类型，方便管理和使用，function 中bool为返回值，int为形参
写法二：
class Solution { public: bool safe(int x,vector<vector<int>>& graph,vector<int>& color){ if(color[x]>0){ return color[x]==2; } color[x]=1; for(int y:graph[x]){ if(!safe(y,graph,color)) return false; } color[x]=2; return true; } vector<int> eventualSafeNodes(vector<vector<int>>& graph) { int n=graph.size(); vector<int> color(n); vector<int> res; for(int i=0;i<n;i++){ if(safe(i,graph,color)) res.push_back(i); } return res; } };
