My Java answer using topological sort


  • -2
    W

    The idea is simple, remove the course with no prerequisites every time and remove their dependency . Basically, it is topological sort.

    public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        HashMap<Integer,ArrayList<Integer>> pre_map = new HashMap<Integer,ArrayList<Integer>>();
        //put every course into pre_map
        for(int i=0;i<numCourses;i++){
            pre_map.put(i,new ArrayList<Integer>());
        }
        //put every prerequisites course into map
        for(int i=0;i<prerequisites.length;i++){
            if(!pre_map.get(prerequisites[i][1]).contains(prerequisites[i][0])){
                pre_map.get(prerequisites[i][1]).add(prerequisites[i][0]);
            }
        }
        Queue<Integer> q = new LinkedList<Integer>();
        Queue<Integer> remove = new LinkedList<Integer>();
        for(int i=0;i<numCourses;i++){
                if(pre_map.containsKey(i)){
                    if(pre_map.get(i).size()==0){
                        q.add(i);
                        pre_map.remove(i);
                    }
                }
            }
        while(!q.isEmpty()){
            int temp = q.poll();
            for(ArrayList al:pre_map.values()){
                al.remove(new Integer(temp));
            }
            for(Integer i:pre_map.keySet()){
                if(pre_map.get(i).size()==0){
                    q.add(i);
                    remove.add(i);
                }
            }
            while(!remove.isEmpty()){
                pre_map.remove(remove.poll());
            }
            
        }
        return (pre_map.isEmpty());
    }
    }

Log in to reply
 

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