# Standard algorithm of detecting cycle in directed graph - Java, runtime 6m

• public class Solution {

``````public boolean canFinish(int numCourses, int[][] prerequisites) {
Graph g = new Graph(prerequisites, numCourses);
return checkCycle(g, numCourses);
}

private class Graph {
private ArrayList<Integer>[] neighbors;

public Graph(int[][] edges, int numCourses) {
neighbors = (ArrayList<Integer>[])new ArrayList[numCourses];
for(int i = 0; i < neighbors.length; i++) {
neighbors[i] = new ArrayList<Integer>();
}
for(int i = 0; i < edges.length; i++) {
}
}

public ArrayList<Integer> getNeighbors(int v) {
return (ArrayList<Integer>)neighbors[v];
}
}

public boolean checkCycle(Graph g, int numCourses) {
boolean[] visited = new boolean[numCourses];
boolean[] visiting = new boolean[numCourses];

for(int i = 0; i < numCourses; i++){
if(dfs(g, i, numCourses, visited, visiting))
return false;
}
return true;
}

public boolean dfs(Graph g, int v, int numCourses, boolean[] visited, boolean[] visiting) {
if(!visited[v]){
visited[v] = true;
visiting[v] = true;

ArrayList<Integer> neighbors = g.getNeighbors(v);
for(Iterator<Integer> it = neighbors.iterator(); it.hasNext();) {
Integer neighbor = (Integer)it.next();
if(!visited[neighbor] && dfs(g, neighbor, numCourses, visited, visiting))
return true;
else if(visiting[neighbor])
return true;
}

}
visiting[v] = false;
return false;
}
``````

}

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