207. 课程表

  1. class Solution {
  2.     public boolean canFinish(int numCourses, int[][] prerequisites) {
  3.         int len=prerequisites.length;
  4.         if(len==0) return true;
  5.         int[] pre=new int[numCourses];
  6.         HashSet<Integer>[] after=new HashSet[numCourses];
  7.         for(int i=0;i<numCourses;i++){
  8.             after[i]=new HashSet<>();
  9.         }
  10.         for(int[] p:prerequisites){
  11.             pre[p[0]]++;
  12.             after[p[1]].add(p[0]);
  13.         }
  14.         int count=0;
  15.         LinkedList<Integer> queue=new LinkedList<>();
  16.         for(int i=0;i<numCourses;i++){
  17.             if(pre[i]==0){
  18.                 queue.offer(i);
  19.             }
  20.         }
  21.         while(!queue.isEmpty()){
  22.             int finished=queue.poll();
  23.             count++;
  24.             for(int i:after[finished]){
  25.                 pre[i]--;
  26.                 if(pre[i]==0){
  27.                     queue.offer(i);
  28.                 }
  29.             }
  30.         }
  31.         return count==numCourses;
  32.     }
  33. }