Java DFS double cache visiting each vertex once 433ms

• ``````public class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
for (int i = 0; i < numCourses; i++) adj.add(i, new ArrayList<>());
boolean[] visited = new boolean[numCourses];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < numCourses; i++) {
if (!topologicalSort(adj, i, stack, visited, new boolean[numCourses])) return new int[0];
}
int i = 0;
int[] result = new int[numCourses];
while (!stack.isEmpty()) {
result[i++] = stack.pop();
}
return result;
}

private boolean topologicalSort(List<List<Integer>> adj, int v, Stack<Integer> stack, boolean[] visited, boolean[] isLoop) {
if (visited[v]) return true;
if (isLoop[v]) return false;
isLoop[v] = true;
for (Integer u : adj.get(v)) {
if (!topologicalSort(adj, u, stack, visited, isLoop)) return false;
}
visited[v] = true;
stack.push(v);
return true;
}
}``````

• Your coding style is clean. I have similar solution and it works in 12ms :

``````public class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<List<Integer>> prereqs = new ArrayList<>();
for(int course=0;course<numCourses;course++){
}

for(int i=0; i<prerequisites.length;i++){
}

boolean[] visited = new boolean[numCourses];
boolean[] visiting = new boolean[numCourses];
Stack<Integer> ordered = new Stack<>();
boolean isCycle = false;
for(int course=0;course<numCourses;course++){
if(!isCycle && !visited[course]){
isCycle = exploreOrder(prereqs,course,visited,visiting,ordered);
}
}
if(isCycle){
return new int[0];//failed
}
int[] res = new int[numCourses];
for(int course=numCourses-1;course>=0;course--){
res[course] = ordered.pop();
}
return res;
}

public boolean exploreOrder(List<List<Integer>> prereqs,int course,boolean[] visited,boolean[] visiting, Stack<Integer> ordered){
if(visiting[course]){
//System.out.println("Cycle found");
return true;
}
visiting[course] = true;
List<Integer> coursePrereqs = prereqs.get(course);
boolean isCycle = false;
for(int prereqCourse=0; prereqCourse<coursePrereqs.size();prereqCourse++){
if(!isCycle) isCycle=exploreOrder(prereqs,coursePrereqs.get(prereqCourse),visited,visiting,ordered);
}
if (!visited[course]){
ordered.push(course);
}
visiting[course] = false;
visited[course] = true;
return isCycle;
}
}
``````

• I replaced the two boolean arrays with one int array where I track the state -

0 - denotes not visited
1 - denotes visiting
2 - denotes visited

Here is the modified code:

``````public int[] findOrder(int numCourses, int[][] prerequisites) {
for (int i = 0; i < numCourses; i++) adj.add(i, new ArrayList<>());
int[] visited = new int[numCourses];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < numCourses; i++) {
if (!topologicalSort(adj, i, stack, visited)) return new int[0];
}
int i = 0;
int[] result = new int[numCourses];
while (!stack.isEmpty()) {
result[i++] = stack.pop();
}
return result;
}

private boolean topologicalSort(List<List<Integer>> adj, int v, Stack<Integer> stack, int[] visited) {
if (visited[v] == 2) return true;
if (visited[v] == 1) return false;
visited[v] = 1;
for (Integer u : adj.get(v)) {
if (!topologicalSort(adj, u, stack, visited)) return false;
}
visited[v] = 2;
stack.push(v);
return true;
}
``````

• This post is deleted!

• Wow, nice solution! I think your solution is more elegant than the top voted!

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