Find Eventual Safe States - Two Solutions - Topological Sort & DFS [JS]

Description 

Solution 1: Topological Sort on Reversed Graph

1. Reverse the graph - we want to traverse the nodes backwards (starting from terminal nodes)
2. Topological sort on the reversed graph,
   Any nodes that end up with an indegree of 0 is a safe node.

n = number of nodes, m = number of edges
Time Complexity: O(n log(n) + m) (including sorting) 253ms
Space Complexity: O(n) 61MB

var eventualSafeNodes = function(graph) {
  let n = graph.length, reversed = Array(n).fill(0).map(() => []);
  let queue = [], indegrees = Array(n).fill(0);
  for (let i = 0; i < n; i++) {
    indegrees[i] = graph[i].length;
    if (indegrees[i] === 0) queue.push(i);
    for (let node of graph[i]) {
      reversed[node].push(i);
    }
  }
  
  let res = [];
  while (queue.length) {
    let node = queue.shift();
    res.push(node);
    for (let i = reversed[node].length; i >= 0; i--) {
      let nei = reversed[node].pop();
      indegrees[nei]--;
      if (indegrees[nei] === 0) queue.push(nei);
    }
  }
  return res.sort((a, b) => a - b);
};

Solution 2: DFS w/ Node Coloring

DFS with node coloring.
Node colors

• 0: not visited
• 1: visited, not in a cycle
• 2: visited, in a cycle

While a node and its neighbors are still in traversal, the node's color is 2.
When traversal for a node and its neighbors are finished, the node's color is 1.

If we traverse a node with a color of 2, we know we have found a cycle.

Time Complexity: O(n + m) 115ms
Space Complexity: O(n) 51MB

var eventualSafeNodes = function(graph) {
  let n = graph.length, color = Array(n).fill(0);
  let res = [];
  for (let i = 0; i < n; i++) {
    if (dfs(i) === 1) res.push(i);
  }
  return res;
  
  function dfs(node) {
    if (color[node] !== 0) return color[node];
    color[node] = 2;
    for (let nei of graph[node]) {
      if (dfs(nei) === 2) return color[node];
    }
    return color[node] = 1;
  }
};

javascript