# 11 ms Java DFS solution, Easy to understand

• Self explanatory Java DFS solution

``````public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> glist = new ArrayList<List<Integer>>();
//Create a graph from the input
for(int i = 0; i < numCourses; ++i) {
glist.add(new ArrayList());
}
for(int i = 0; i < prerequisites.length; ++i) {
glist.get(prerequisites[i][1]).add(prerequisites[i][0]);
}

boolean visited[] = new boolean[numCourses];
Set<Integer> check = new HashSet();  // Create a set for checking whether the node being processed is visited again

for(int i = 0; i < numCourses; ++i) {
if(hasCycle(i, glist, check, visited) == true) return false;
}

return true;
}

private boolean hasCycle(int course,List<List<Integer>> glist, Set<Integer> check, boolean[] visited) {
if(!visited[course]) {
visited[course] = true;
check.add(course); // Add the current node to the set
for(int i = 0; i < glist.get(course).size(); ++i) { // for each node in the graph
if(!visited[glist.get(course).get(i)] && hasCycle(glist.get(course).get(i), glist, check, visited)) return true; // recursive dfs call
else if(check.contains(glist.get(course).get(i))) return true; // Current node is visited twice, so there is a cycle
}
}
check.remove(course); // once the current node is processed, remove it from the set and move on to the next node
return false;
}
}
``````

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