My Java BFS solution


  • 0
    F

    My Java BFS solution, easy to understand

    class Solution {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            ArrayList[] graph = new ArrayList[numCourses];
            for (int i = 0; i < numCourses; i++) {
                graph[i] = new ArrayList();
            }
            int[] indegree = new int[numCourses];
            for (int i = 0; i < prerequisites.length; i++) {
                indegree[prerequisites[i][0]]++;
                graph[prerequisites[i][1]].add(prerequisites[i][0]);
            }
            
            int count = 0;
            int[] order = new int[numCourses];
            int index = 0;
            
            Queue<Integer> que = new LinkedList<>();
            
            for (int i = 0; i < indegree.length; i++) {
                if (indegree[i] == 0) {
                    que.offer(i);
                    order[index++] = i;
                    count++;
                }
            }
            
            while (!que.isEmpty()) {
                int course = que.poll();
                
                for (int i = 0; i < graph[course].size(); i++) {
                    int pre = (int)graph[course].get(i);
                    indegree[pre]--;
                    if (indegree[pre] == 0) {
                        que.offer(pre);
                        order[index++] = pre;
                        count++;
                    }
                }
            }
            return count == numCourses ? order : new int[0];
            
            
        }
    }
    
    

Log in to reply
 

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