# Java directed cycle detection solution in 8ms. Beat 84.40% Java solution

• The idea is trivial depth first search, a simpler variance of 'Directed cycle detection' solution originated from Algorithms 4th edition.
https://github.com/zeqli/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/DirectedCycle.java

1. Construct an adjacent list
2. Keep track of visited vertice (boolean[] marked) and current visiting path (boolean[] onStack)
3. If there is a vertex that has been on stack appears in another vertex's adjacent list, then we find a cycle.
``````public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
boolean[] marked = new boolean[numCourses];
boolean[] onStack = new boolean[numCourses];
List<List<Integer>> adj = new ArrayList<>(numCourses);
for (int i = 0; i < numCourses; i++){
adj.add(new ArrayList<>());
}

for (int[] pair: prerequisites){
List<Integer> list = adj.get(pair[0]);
list.add(pair[1]);
}

for (int i = 0; i < numCourses; i++){
boolean canFinish = true;
if (!marked[i])
canFinish = dfs(adj, i, marked, onStack);
if (!canFinish)
return false;
}
return true;
}

public boolean dfs(List<List<Integer>> adj, int v, boolean[] marked, boolean[] onStack){
onStack[v] = true;
marked[v] = true;
for (int w : adj.get(v)){
boolean canFinish = true;
if (!marked[w]){
canFinish = dfs(adj, w, marked, onStack);
} else if (onStack[w]){
canFinish = false;
}
if (!canFinish)
return false;
}
onStack[v] = false;
return true;
}
}
``````

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