My JAVA DFS solution


  • 0
    Q
    public class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            Map<Integer, Set<Integer>> courseToPrereqs = new HashMap<Integer, Set<Integer>>();
            for (int i=0;i<prerequisites.length;i++){
                int courseId = prerequisites[i][0];
                int prereqId = prerequisites[i][1];
                
                Set<Integer> prereqs = courseToPrereqs.get(courseId);
                if (prereqs == null){
                	prereqs = new HashSet<Integer>();
                	courseToPrereqs.put(courseId, prereqs);
                }
                prereqs.add(prereqId);
            }
            boolean[] cycleDetector = new boolean[2500];
            boolean[] visitedEarlier = new boolean[2500];
            for (int i=0;i<numCourses;i++){
            	if (!validate(cycleDetector, i, courseToPrereqs, visitedEarlier)){
                	return false;
                }            
            }
            return true;
        }
        private boolean validate(boolean[] cycleDetector, Integer course, Map<Integer, 
            Set<Integer>> courseToPrereqs,  boolean[] visitedEarlier){
            if (visitedEarlier[course]){ 
                return true;
            }
        	if (cycleDetector[course]){
        		return false;
        	}
        	Set<Integer> prereqs = courseToPrereqs.get(course);
        	
        	cycleDetector[course] = true;
        	if (prereqs != null){
            	for (int prereq:prereqs){
            		if (!validate(cycleDetector, prereq, courseToPrereqs, visitedEarlier)){
            			return false;
            		}
            	}
        	}
        	visitedEarlier[course] = true;
        	return true;
        }
    }

Log in to reply
 

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