Question: Java BFS method exceeds time limit on 2000 courses case


  • 0
    L
    public boolean canFinish(int numCourses, int[][] prerequisites) {
    
    	
    	if (numCourses == 0) { return true; }
    	if (prerequisites.length == 0 || prerequisites[0].length == 0) {
    		return true;
    	}
    	
    	
    	//Build a graph
    	Map<Integer, Set<Integer>> graph = new HashMap<Integer, Set<Integer>>();
    	for (int i = 0; i < numCourses; i++) {
    		graph.put(i, new HashSet<Integer>());
    	}
    	for (int[] pair : prerequisites) {
    		graph.get(pair[0]).add(pair[1]);
    	}
    	
    	// A queue for track exploring courses in FIFO
    	Queue<Integer> queue = new LinkedList<Integer>();
    	
    	// number of courses/node explored related to BFS
    	int remaining = numCourses;
    	
    	// First, find the tip in the graph, or the course with no prerequisites
    	// These are the starting point in our BFS
    	for (int course: graph.keySet()) {
    		if (graph.get(course).size() == 0) {
    			
    			// if a course has 0 prerequisites, it can be taken
    			queue.offer(course);
    			remaining--;
    		}
    	} // if there no course to start, while graph is cycle
        
    	while (!queue.isEmpty()) {
    		int course = queue.poll(); 
    		
    		for (Map.Entry<Integer, Set<Integer>> entry: graph.entrySet()) {
    			// Go through all courses' list, check if it has this course as a prerequisite
    			if (entry.getValue().contains(course)) {
    				entry.getValue().remove(course);
    				
    				if (entry.getValue().isEmpty()) {
    					queue.offer(entry.getKey());
    					remaining--;
    				}
    			}
    		}
    	} // end while
    	
    	return remaining == 0;
    } // end canFinish() functionn

Log in to reply
 

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