breadth first search


  • 0
    F
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            @SuppressWarnings("unchecked")
            ArrayList<Integer>[] graph = (ArrayList<Integer>[]) new ArrayList[numCourses];
            for (int i = 0; i < numCourses; i++) {
                graph[i] = new ArrayList<>();
            }
            int[] inDegrees = new int[numCourses];
            for (int[] prerequisite : prerequisites) {
                graph[prerequisite[1]].add(prerequisite[0]);
                inDegrees[prerequisite[0]]++;
            }
            Queue<Integer> queue = new LinkedList<>();
            List<Integer> result = new ArrayList<>();
            for (int i = 0; i < inDegrees.length; i++) {
                if (inDegrees[i] == 0) {
                    queue.offer(i);
                    result.add(i);
                }
            }
            while (!queue.isEmpty()) {
                Integer v = queue.poll();
                for (Integer w : graph[v]) {
                    if (--inDegrees[w] == 0) {
                        queue.offer(w);
                        result.add(w);
                    }
                }
            }
            if (result.size() < numCourses) {
                return new int[0];
            } else {
                int[] answer = new int[numCourses];
                for (int i = 0; i < numCourses; i++) {
                    answer[i] = result.get(i);
                }
                return answer;
            }
        }

Log in to reply
 

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