Java BFS Solution, very easy to understand!!


  • 1
    V
    public class Solution {
        public int[] findOrder(int n, int[][] pre) {
            Map<Integer, List<Integer>> map=new HashMap<Integer, List<Integer>>();
            LinkedList<Integer> orderList=new LinkedList<Integer>();
            int[] indegree=new int[n];
            for(int i=0; i<n; i++){
                map.put(i,new ArrayList<Integer>());
            }
            
            for(int i=0; i<pre.length; i++){
                map.get(pre[i][0]).add(pre[i][1]);
                indegree[pre[i][1]]++;
            }
            Queue<Integer> queue=new LinkedList<Integer>();
            for(int i=0; i<n; i++){
                if(indegree[i]==0){
                    queue.offer(i);
                    orderList.addFirst(i);
                }
            }
            int count=n;
            while(!queue.isEmpty()){
                int cur=queue.poll();
                for(int child : map.get(cur)){
                    if(--indegree[child]==0){
                        queue.offer(child);
                        orderList.addFirst(child);
                    }
                }
                count--;
            }
            if(count!=0){
                return new int[0];
            }
            int[] order=new int[orderList.size()];
            for(int i=0; i<order.length; i++){
                order[i]=orderList.get(i);
            }
            return order;
        }
    }

  • 0
    C

    @VincentCheng nice solution, we can get rid of list can can use array instead. I used you logic in my code

        public int[] findOrder(int numCourses, int[][] prerequisites) {
            Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
            
            //creating the graph nodes 
            for(int i=0; i<numCourses; i++){
                map.put(i, new ArrayList<Integer>());
            }
            
            // index to record indegree count for each node
            int[] indegree = new int[numCourses];
            for(int i=0; i<prerequisites.length; i++){
                map.get(prerequisites[i][0]).add(prerequisites[i][1]);
                indegree[prerequisites[i][1]]++;
            }
            
            // creating the result array
            int[] result = new int[numCourses];
            int idx = numCourses - 1;
            
            // addling all zero indegree nodes
            Queue<Integer> queue = new LinkedList<Integer>();
            for(int i=0; i<indegree.length; i++){
                if(indegree[i] == 0){
                    queue.add(i);
                    result[idx--] = i;
                }
            }
            
            // doing a breadth first search
            while(!queue.isEmpty()){
                int top = queue.poll();
                for(int child : map.get(top)){
                    if(--indegree[child] == 0){
                        queue.add(child);
                        result[idx--] = child;
                    }
                }
            }
            
            // checking for cyclic dependency
            if(idx != -1){
                return new int[0];
            }
            
            return result;
        }
    

Log in to reply
 

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