Java Easy BFS solution


  • 0
    S
    public int[] findOrder(int numCourses, int[][] prerequisites) {
            int[] indegree = new int[numCourses];
            int[] result = new int[numCourses];
            HashMap<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>();
            
            for (int i = 0; i < prerequisites.length; i++) {
                int v = prerequisites[i][0];
                int d = prerequisites[i][1];
                HashSet<Integer> set = map.get(v);
                if (set == null) set = new HashSet<Integer>();
                if (set.add(d)) {
                    indegree[d]++;
                    map.put(v, set);
                }
            }
            
            Queue<Integer> queue = new LinkedList<Integer>();
            for (int i = 0; i < indegree.length; i++) {
                if (indegree[i] == 0) queue.offer(i);
            }
            
            int i = numCourses - 1;
            while(!queue.isEmpty()) {
                int v = queue.poll();
                result[i--] = v;
                if (map.containsKey(v)) {
                    for (int d : map.get(v)) {
                        if (--indegree[d] == 0) queue.offer(d);
                    }
                }
            }
            return i >= 0 ? new int[0] : result;
        }
    

Log in to reply
 

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