LeetCode/java/find-eventual-safe-states.java

class Solution {
  private static class DFS {
    private int[][] graph;
    private boolean[] visited;
    private boolean[] open;

    public DFS(int[][] graph) {
      this.graph = graph;
      visited = new boolean[graph.length];
      open = new boolean[graph.length];
    }

    public boolean hasInCycle(int u) {
      return open[u];
    }

    public boolean run(int u) {
      if (open[u]) {
        // found loop
        return true;
      }

      if (visited[u]) {
        // searched vertex
        return false;
      }

      visited[u] = true;

      open[u] = true;
      for (var v : graph[u]) {
        if (run(v)) {
          // loops stay open
          return true;
        }
      }
      open[u] = false;

      return false;
    }
  }

  public List<Integer> eventualSafeNodes(int[][] graph) {
    int n = graph.length;

    var runner = new DFS(graph);
    for (var i = 0; i < n; ++i) {
      runner.run(i);
    }

    var safe = new ArrayList<Integer>();
    for (var i = 0; i < n; ++i) {
      if (!runner.hasInCycle(i)) {
        safe.add(i);
      }
    }

    return safe;
  }
}