# Java 13ms Iterative DFS solution with Explanation

• Just FYI, here is my solution for the other problem: Course Schedule.

Mapping of element value in `visited` array to colors in CLRS DFS algorithm:
0 -> White, -1 -> Gray, 1 -> Black

We need to peek a node in stack for the first time, and pop it for the second time we meet it. In other words, we need to keep a node in stack until the dfs search rooted at it has been finished, which is equivalent to the end of a recursive call.

For the end of the corresponding dfs search rooted at `prere`: -1 corresponding to `prere` as a normal node; 1 corresponding to `prere` as an end node of a cross edge.

My Java implementation of the iterative DFS algorithm based on its recursive counterpart in CLRS (13ms):

``````public class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] visited = new int[numCourses];
List<List<Integer>> graph = new ArrayList<>();
ArrayDeque<Integer> stack = new ArrayDeque<>();
ArrayDeque<Integer> auxStack = new ArrayDeque<>();
int[] order = new int[numCourses];

for (int i = 0; i < numCourses; i++) {
}
for (int i = 0; i < prerequisites.length; i++) {
int course = prerequisites[i][0], prere = prerequisites[i][1];
}

for (int i = 0; i < numCourses; i++) {
if (visited[i] == 0) {
stack.push(i);
while (!stack.isEmpty()) {
Integer prere = stack.peek();
if(visited[prere] == 0) {
// start of dfs search rooted at prere
visited[prere] = -1;
}
else if (visited[prere] == -1){
// end of dfs search rooted at prere; prere is a normal node
stack.pop();
visited[prere] = 1;
auxStack.push(prere);
continue;
}
else if (visited[prere] == 1) {
// since prere is an end node of a cross edge; the dfs search rooted at prere
// has been finished as part of another dfs search rooted at another node
// we have no need to explore its neighbors again
stack.pop();
continue;
}
for (Integer course: graph.get(prere)) {
if (visited[course] == 0) {
stack.push(course);
}
else if (visited[course] == -1) {
return new int[0];
}
}
}

}
}
for (int i = 0; i<numCourses; i++) {
order[i] = auxStack.pop();
}
return order;
}
}
``````

Just for comparison, here is my Java implementation of the recursive DFS algorithm in CLRS (8ms):

``````public class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] visited = new int[numCourses];
ArrayDeque<Integer> stack = new ArrayDeque<Integer>();
List<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < numCourses; i++) {
}
for (int i = 0; i < prerequisites.length; i++) {
}

for (int i = 0; i < numCourses; i++) {
if (visited[i] == 0 && dfsDetectCycle(graph, visited, stack, i)) return new int[0];
}
int[] order = new int[numCourses];
for (int i = 0; i < numCourses; i++)
order[i] = stack.pop();
return order;
}

private boolean dfsDetectCycle(List<ArrayList<Integer>> graph, int[] visited,
ArrayDeque<Integer> stack, int prere) {
visited[prere] = -1; //Gray
for (int course: graph.get(prere)) {
if (visited[course] == -1) return true;
else if (visited[course] == 0 && dfsDetectCycle(graph, visited, stack, course)) return true;
}
visited[prere] = 1; //Black
stack.push(prere);
return false;
}
}
``````

My Java implementation of the BFS solution with indegree (11ms):

``````public class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] indegree = new int[numCourses];
List<List<Integer>> graph = new ArrayList<>();
Queue<Integer> queue = new ArrayDeque<>();
int count = 0;
int[] order = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
}
for (int i = 0; i < prerequisites.length; i++) {
int course = prerequisites[i][0], prere = prerequisites[i][1];
indegree[course]++;
}
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0)
queue.offer(i);
}

while (!queue.isEmpty()) {
Integer prere = queue.poll();
order[count++] = prere;
for (Integer course: graph.get(prere)) {
if (--indegree[course] == 0)
queue.offer(course);
}
}
if(count == numCourses) {
return order;
}
else {
return new int[0];
}
}
}
``````

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