11 ms Java DFS solution, Easy to understand


  • 1

    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;
        }
    }
    

Log in to reply
 

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