Java BSF solution


  • 0
    B

    I maintained two HashSet array: preSets and postSets.
    preSets[i] is the course set that should be taken directly before ith course;
    postSets[i] is the course set that should be taken directly after ith course;

    Also a set about the un-taken courses is used here; in the BSF, for each round, the un-taken course which prerequisite course is already taken will be processed. The BSF loop will be breaked(function will be returned) when no course could be taken, we check if we had already taken all the courses.

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        @SuppressWarnings("unchecked")
        Set<Integer>[] preSets  = new Set[numCourses], 
                       postSets = new Set[numCourses];
        Set<Integer> untaken = new HashSet<>();
        for(int i = 0; i < numCourses; i++){
            preSets[i] = new HashSet<>();
            postSets[i] = new HashSet<>();
            untaken.add(i);
        }
        for(int[] p: prerequisites){
            preSets[p[1]].add(p[0]);
            postSets[p[0]].add(p[1]);
        }
        
        Set<Integer> taking = new HashSet<>();
        while(true){
            for(int i: untaken)
                if(preSets[i].isEmpty()){
                    taking.add(i);
                    for(int cur: postSets[i])
                        preSets[cur].remove(i);
                }
            if(taking.isEmpty())
                return untaken.isEmpty();
            untaken.removeAll(taking);
            taking.clear();
        }
    }

  • 0
    G
    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses == 0 || prerequisites.length == 0 || prerequisites[0].length == 0 )
            return true;
        HashMap<Integer, HashSet<Integer>> graph = buildMap(numCourses, prerequisites);
        HashMap<Integer, HashSet<Integer>> inMap = buildInD(numCourses, prerequisites);
        int canFinished = topoSort(graph, inMap,numCourses);
        return canFinished == numCourses;
        
    }
    private static HashMap<Integer, HashSet<Integer>> buildMap( int numCourses, int[][] prerequisites){//to do BFS traversal 
        HashMap<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>();
        for(int i = 0; i < prerequisites.length; i++){
            if(!map.containsKey(prerequisites[i][1])){
                map.put(prerequisites[i][1], new HashSet<Integer>());
            }
            map.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        return map;
    }
    
    private static HashMap<Integer, HashSet<Integer>> buildInD( int numCourses, int[][] prerequisites){//to topoSort
        HashMap<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>();
        for(int i = 0; i < prerequisites.length; i++){
            if(!map.containsKey(prerequisites[i][0])){
                map.put(prerequisites[i][0], new HashSet<Integer>());
            }
            map.get(prerequisites[i][0]).add(prerequisites[i][1]);
        }
        return map;
    }
    
    private static int topoSort(HashMap<Integer, HashSet<Integer>> graph , HashMap<Integer, HashSet<Integer>> inMap,int numCourses){
        Queue<Integer> q = new LinkedList<Integer>();
        Set<Integer> finished = new HashSet<Integer>();
        for(int i = 0; i < numCourses; i++){
            if(!inMap.containsKey(i))
            q.offer(i);
        }
        while(!q.isEmpty()){
            int n = q.poll();
            finished.add(n);
            if(graph.get(n) != null)
            for(int i : graph.get(n)){
            	
                inMap.get(i).remove(n);
                if(inMap.get(i).size() == 0)
                    q.offer(i);
            }
        }
        return finished.size();
        
    }

Log in to reply
 

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