# Simple Java solution using DFS to check if a back edge exists; Beats 95.59% of submissions

• This is a simple method to detect a cycle using dfs. This method basically checks if a back edge exists in the graph. Its a simple 2 step process.
Step 1: construct a graph out of the prerequesite array.
Step 2 : perform dfs. While performing dfs, keep track of the current vertex being explored in the recursion in an array say currentStack. If we encounter a vertex which is already in the currentStack, it means there is a loop in the graph.

``````public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {

List<Integer> graph[] = new ArrayList[numCourses];
for(int i = 0; i < numCourses; i++){
graph[i] = new ArrayList<Integer>();
}

boolean[] visited = new boolean[numCourses];
boolean[] currentStack = new boolean[numCourses];

for(int i = 0; i < prerequisites.length; i++){
}
for(int i = 0; i < numCourses; i++){
if(isCycle(graph, visited, currentStack, i)){
return false;
}
}
return true;
}

private boolean isCycle(List<Integer> adj[], boolean[] visited, boolean[] currentStack, int start){

visited[start] = true;
currentStack[start] = true;
while(it.hasNext()){
int temp = it.next();
if(!visited[temp] && isCycle(adj, visited, currentStack, temp)){
return true;
}else if(currentStack[temp]){
return true;
}
}
currentStack[start] = false;
return false;
}
}
``````

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