DFS based Topological Sort algorithm in Java (beats 89.24% of javasubmissions)

• ``````public int[] findOrder(int numCourses, int[][] prerequisites) {
ArrayList<Integer>[] graph = new ArrayList[numCourses];
for(int i = 0; i < numCourses; i++) {
graph[i] = new ArrayList<>();
}
for (int[] pre : prerequisites) {
}

boolean[] visited = new boolean[numCourses];
boolean[] onStack = new boolean[numCourses];

if (hasCircle(graph, visited, onStack, reversePost)) {
return new int[0];
}

int[] res = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
res[i] = reversePost.pop();
}

return res;

}

private boolean hasCircle(ArrayList<Integer>[] graph, boolean[] visited, boolean[] onStack, Deque<Integer> reversePost) {
for(int i = 0; i < graph.length; i++) {
if (!visited[i]) {
if (dfs(graph, visited, onStack, i, reversePost)) {
return true;
}
}
}
return false;
}

private boolean dfs(ArrayList<Integer>[] graph, boolean[] visited, boolean[] onStack, int i, Deque<Integer> reversePost) {
onStack[i] = true;
visited[i] = true;
for (int j : graph[i]) {
if (!visited[j]) {
if (dfs(graph, visited, onStack, j, reversePost)) {
return true;
}
} else if (onStack[j]) {
return true;
}
}
onStack[i] = false;
reversePost.push(i);
return false;
}``````

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