My Java BFS solution


  • 14
    S
    public class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            Map<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
            int[] indegree = new int[numCourses];
            Queue<Integer> queue = new LinkedList<Integer>();
            int count = numCourses;
            for (int i = 0; i < numCourses; i++) {
                map.put(i, new ArrayList<Integer>());
            }
            for (int i = 0; i < prerequisites.length; i++) {
                map.get(prerequisites[i][0]).add(prerequisites[i][1]);
                indegree[prerequisites[i][1]]++;
            }
            for (int i = 0; i < numCourses; i++) {
                if (indegree[i] == 0) {
                    queue.offer(i);
                }
            }
            while (!queue.isEmpty()) {
                int current = queue.poll();
                for (int i : map.get(current)) {
                    if (--indegree[i] == 0) {
                        queue.offer(i);
                    }
                }
                count--;
            }
            return count == 0;
        }
    }

  • -6
    Z

    just use topo theory. a simple solution.

    public class Solution {
            public boolean canFinish(int numCourses, int[][] prerequisites) {
                if(numCourses<=1) return true;
                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]);
                }
                HashSet<Integer> finished=new HashSet<Integer>();
                for(int i=0;i<numCourses;++i)
                    if(!map.containsKey(i))
                        finished.add(i);
                while(map.size()>0){
                    if(!find(map,finished))
                        return false;
                }
                return true;
            }
            boolean find(HashMap<Integer,HashSet<Integer>> map,HashSet<Integer> finished){
                for(Integer key: map.keySet()){
                    HashSet<Integer> values=map.get(key);
                    if(finished.containsAll(values)){
                        finished.add(key);
                        map.remove(key);
                        return true;
                    }
                }
                return false;
            }
        }

  • 0
    K

    How about if the input is multiple connected components, your solution seems cannot handle this situation.


  • 0
    A

    Brilliant code


  • 0
    J

    What does multiple connected components mean?@kangwang


Log in to reply
 

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