# Java 5-6ms (> 97-99%) , very concise and very fast DFS, with explanation

• I ran it about 10 times, 2/10 times it ran in 5 ms, maybe I got lucky. The average run is 6 ms.

Cycle detection is inside the dfs routine - standard 3-color approach.

At first I tried to create an adjacency list with edges directed from the prerequisite to the given course, and then reverse the result of the topological sort.

This is not necessary, we can simply construct the tree in reverse - from given course to its prerequisites - and then simply output the result of the topological sort.

``````public int[] findOrder(int numCourses, int[][] prerequisites) {
List<Integer>[] edges = new ArrayList[numCourses];

// array to track visited nodes and detect cycles, 0 = white, 1 = gray, 2 = black
int[] visited = new int[numCourses];

// output array
int[] res = new int[numCourses];

for (int i = 0; i < edges.length; i++)
edges[i] = new ArrayList<Integer>();
for (int[] edge : prerequisites)

// run topological sort
for (int i = 0, j = 0; i < numCourses; i++) {
j = dfs(i, edges, visited, res, j);
if (j == -1) return new int[0]; // cycle, return empty array
}

return res;
}

/**
* One way to optimize the dfs is to initialize the output array of desired size
* and pass the index of the current slot in the array.
* 2. We recursively pass this index through the calls until we get to our first black node.
* 3. We set res[index] = our black node.
* 4. We then return index + 1, so that the next black node we find will be inserted in the next slot of res.
*/
private int dfs(int v, List<Integer>[] edges, int[] visited, int[] res, int i) {
if (visited[v] == 2) return i;           // black node
if (visited[v] == 1) return -1;          // gray node -> cycle
visited[v] = 1;
for(int j : edges[v]) {
i = dfs(j, edges, visited, res, i);
if (i == -1) return -1;              // if there is a cycle, propagate the error
}
visited[v] = 2;
res[i] = v;
return i+1;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.