一、题目

在有向图中，以某个节点为起始节点，从该点出发，每一步沿着图中的一条有向边行走。如果到达的节点是终点（即它没有连出的有向边），则停止。

对于一个起始节点，如果从该节点出发，无论每一步选择沿哪条有向边行走，最后必然在有限步内到达终点，则将该起始节点称作是 安全 的。

返回一个由图中所有安全的起始节点组成的数组作为答案。答案数组中的元素应当按 升序 排列。

该有向图有 n 个节点，按 0 到 n - 1 编号，其中 n 是 graph 的节点数。图以下述形式给出：graph[i] 是编号 j 节点的一个列表，满足 (i, j) 是图的一条有向边。

点击查看原题
难度级别： 中等

二、思路

1）三色标记法

利用三色标记法可以记录下状态，凡是遍历过的都会被标记上颜色，令0为未访问过，1为不可达或在dfs栈中，2为安全节点。凡只能到达2节点或出度为0的，颜色都为2，只要能到达颜色1，都染色为1.

2）拓补排序

能够只达到安全节点的节点，其出度一定都在安全节点上，所以我们反向建表，以安全节点为起点，进行拓补排序，遍历到节点会将其出度减1，整体都遍历结束后，出度不为0的节点为非安全节点。

三、代码

1）三色标记法

  1. class Solution {
  2.     public List<Integer> eventualSafeNodes(int[][] graph) {
  3.         int[] color = new int[graph.length];
  4.         List<Integer> ans = new ArrayList();
  5.         for (int i = 0; i < graph.length; i++) {
  6.             if (isSafe(graph, color, i)) {
  7.                 ans.add(i);
  8.             }
  9.         }
  10.         return ans;
  11.     }
  12.     public boolean isSafe(int[][] graph, int[] color, int node) {
  13.         if (color[node] > 0) {
  14.             return color[node] == 2;
  15.         }
  16.         color[node] = 1;
  17.         for (int next : graph[node]) {
  18.             if (!isSafe(graph, color, next)) {
  19.                 return false;
  20.             }
  21.         }
  22.         color[node] = 2;
  23.         return true;
  24.     }
  25. }

时间复杂度为O(m+n)，空间复杂度为O(n)

2）拓补排序

  1. class Solution {
  2.     public List<Integer> eventualSafeNodes(int[][] graph) {
  3.         List<List<Integer>> reverseG = new ArrayList();
  4.         int[] inDegree = new int[graph.length];    // 反向建图后，原图的出度为反向图入度
  5.         // 逆向图并初始化
  6.         for (int i = 0; i < graph.length; i++) {
  7.             reverseG.add(new ArrayList());
  8.         }
  9.         for (int i = 0; i < graph.length; i++) {
  10.             for (int j : graph[i]) {
  11.                 reverseG.get(j).add(i);
  12.             }
  13.             inDegree[i] = graph[i].length;
  14.         }
  16.         Queue<Integer> queue = new LinkedList();
  17.         // 将原图为安全节点的节点作为起始节点
  18.         for (int i = 0; i < graph.length; i++) {
  19.             if (graph[i] == null || graph[i].length == 0) {
  20.                 queue.offer(i);
  21.             }
  22.         }
  24.         // 根据起始节点顺序向下遍历，能够安全到达起始节点的入度会降为0，能达到其他非安全节点的就会大于0
  25.         while (!queue.isEmpty()) {
  26.             int node = queue.poll();
  27.             for (int next : reverseG.get(node)) {
  28.                 if (--inDegree[next] == 0) {
  29.                     queue.offer(next);
  30.                 }
  31.             }
  32.         }
  34.         List<Integer> ans = new ArrayList();
  35.         for (int i = 0; i < inDegree.length; i++) {    // 将入度为0的节点汇总成答案
  36.             if (inDegree[i] == 0) {
  37.                 ans.add(i);
  38.             }
  39.         }
  41.         return ans;
  42.     }
  43. }

时间复杂度为O(n+m)，空间复杂度为O(n+m)