2022-04-14 拓扑排序 课程表

210. 课程表 II

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {

        // 入度表  数组
        // 入读=0 队列进去   队列判断是否空
        // List<List<IN>存依赖
        int n=numCourses;
        List<List<Integer>> list=new ArrayList<>();
        List<Integer> ans=new ArrayList<>();
        int[] courseCount=new int[n];
        Queue<Integer>  queue=new LinkedList<Integer>();
        for(int i=0;i<n;i++){
            list.add(new ArrayList<>());
        }
        for(int[] cp:prerequisites){
           courseCount[cp[0]]++;
           list.get(cp[1]).add(cp[0]);
        }
        for(int i=0;i<n;i++){
            if(courseCount[i]==0){
                queue.add(i);
            }
        }
        int count=0;
          int[] res=new int[n];
        // for(int i=0;i<n;i++){
        //     res[i]= ans.get(i);
        // }
        while(!queue.isEmpty()){
            int pre=queue.poll();
            ans.add(pre);
            res[count]=pre;
            count++;
            numCourses--;
           for(int cur:list.get(pre)){
            //    courseCount[cur]--;
               if(--courseCount[cur]==0){
                 queue.add(cur);
               }
           }
        }
        int[] result=numCourses==0?res:new int[]{};
        
        return result;
    }
}