# Explained Java 12ms Iterative DFS solution based on DFS algorithm in CLRS

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

``````public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] visited = new int[numCourses];
List<List<Integer>> graph = new ArrayList<>();
ArrayDeque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < numCourses; i++) {
}
for (int i = 0; i < prerequisites.length; i++) {
int course = prerequisites[i][0], prere = prerequisites[i][1];
}
//mapping of element value in visited array to colors in CLRS DFS algorithm:
//0 -> White, -1 -> Gray, 1 -> Black
for (int i = 0; i < numCourses; i++) {
if (visited[i] == 0) {
stack.push(i);
while (!stack.isEmpty()) {
// 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
Integer prere = stack.peek();
if(visited[prere] == 0) {
visited[prere] = -1;
}
else if (visited[prere] == -1 || visited[prere] == 1) {
// for the end of the corresponding recursive dfs call rooted at prere
//-1 corresponding to prere as a normal node
//1 corresponding to prere as an end node of a cross edge
stack.pop();
visited[prere] = 1;
continue;
}
for (Integer course: graph.get(prere)) {
if (visited[course] == 0) {
stack.push(course);
}
else if (visited[course] == -1) {
return false;
}
}
}

}
}
return true;
}
}
``````

Just for comparison, my solution implementing recursive DFS (7ms):

``````public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] visited = new int[numCourses];
List<List<Integer>> graph = new ArrayList<>();
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, i)) return false;// 0: White
}
return true;
}

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

My implementation of BFS solution using indegree:

``````public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] indegree = new int[numCourses];
List<List<Integer>> graph = new ArrayList<>();
int count = 0;
Queue<Integer> queue = new ArrayDeque<>();
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();
count++;
for (Integer course: graph.get(prere)) {
if (--indegree[course] == 0) {
queue.offer(course);
}
}
}
return count == numCourses;

}
}
``````

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