JAVA BFS easy solution


  • 0
    public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        ArrayList<HashSet<Integer>> adjacent_list = new  ArrayList<HashSet<Integer>>();
        for(int i=0;i<numCourses;i++)
            adjacent_list.add(new HashSet<Integer>());
    
        for(int i=0;i<prerequisites.length;i++){
            adjacent_list.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        
        int[] indegree = new int[numCourses];
        for(int i=0;i<adjacent_list.size();i++){
            for(int x:adjacent_list.get(i))
                 indegree[x]++;
        }
        
        LinkedList<Integer> queue = new LinkedList<Integer>();
        for(int i=0;i<numCourses;i++){
            if(indegree[i] == 0){
                queue.offer(i);
            }
        }
        int[] res = new int[numCourses];
        int count = 0;
        while(!queue.isEmpty()){
            int cur = queue.pollFirst();
            for(int c : adjacent_list.get(cur)){
                if(--indegree[c] == 0)
                    queue.offer(c);
            }
            
            res[count++] = cur;
        }
        return count==numCourses? res: new int[0];
    }
    

    }


  • 0
    S

    My code is similar like you, but I find a problem, what if prerequisites is null, since we don't check that , it will have NullPointerException, when we call prerequisites.length may not pass(although it accepted in OJ).


Log in to reply
 

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