//Runtime: 6 ms, faster than 63.02% of Java online submissions for Course Schedule II.
//Memory Usage: 45.6 MB, less than 85.37% of Java online submissions for Course Schedule II.
class Solution {
  final int PROCESSING = 1;
  final int DONE = 2;
  final int[] NOT_POSSIBLE = new int[0];

  public int[] findOrder(int numCourses, int[][] prerequisites) {
    ArrayList<Integer>[] graph = buildGraph(numCourses,prerequisites);
    int[] states = new int[numCourses];
    LinkedList<Integer> answer = new LinkedList<>();

    for(int i = 0; i < numCourses; i++){
      boolean cycle = dfs(graph, i, answer, states);
      if(cycle) return NOT_POSSIBLE;
    }
    if(answer.size() != numCourses) return NOT_POSSIBLE;
    int[] result = new int[numCourses];
    for(int i = 0; i < numCourses; i ++) result[i] = answer.get(i);
    return result;
  }

  private boolean dfs(ArrayList<Integer>[] graph, int current, LinkedList<Integer> answer, int[] states){
    if(states[current] == PROCESSING){
      return true;
    }
    if(states[current] == DONE) return false;

    states[current] = PROCESSING;
    for(int next : graph[current]){
      if(states[next] == DONE) continue;
      boolean cycle = dfs(graph, next, answer, states);
      if(cycle) return true;
    }
    answer.add(current);
    states[current] = DONE;
    return false;
  }

  ArrayList<Integer>[] buildGraph(int numCourses, int[][] prerequisites){
    ArrayList<Integer>[] graph = new ArrayList[numCourses];
    for(int i = 0 ; i < graph.length; i++) graph[i] = new ArrayList<>();
    for(int[] edge : prerequisites){
      graph[edge[0]].add(edge[1]);
    }
    return graph;
  }
}