2021-12-14 课程表

自己想不出来好的思路，这个题很经典，可以用拓扑排序，也可以用深度优先判定是否是个环来解决，
思路就是建立一个入度数组，一个统计对应关系的arralist，和一个队列。
从入度数组出发，统计零元素放入队列，队列剔除队首元素，并根据arraylist找到对应的下一个元素，
得到下一个元素的入度，若是0，放入队列，继续这样的操作，知道队列是空的，
java版本：

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

// 拓扑排序
// 建立一个入度表，队列，和用来统计对应关系的数组，同时
// 把入度是0的放入队列，同时队列不是空的时候出队首元素，同时入度·表的后向元素减减
int[] arr=new int[numCourses];
int pre;
Queue<Integer> queue=new LinkedList<>();
List<List<Integer>> list =new ArrayList<>();
for (int i=0;i<numCourses;i++){
    list.add(new ArrayList<>());
}
for(int j=0;j<prerequisites.length;j++){
  pre=prerequisites[j][0];
   arr[pre]++;
 list.get(prerequisites[j][1]).add(pre);
}

for(int i=0;i<numCourses;i++){
    // System.out.println("arr:"+arr[i]);
 if(arr[i]==0)
     queue.add(i);
    

}
 while(!queue.isEmpty()){
   pre= queue.poll();
  numCourses--;
//    System.out.println("pre:"+pre);
  for(int cur:list.get(pre)){
      arr[cur]--;
    //    System.out.println("cur:"+cur);
    //    System.out.println("arr[cur]:"+arr[cur]);

      if(arr[cur]==0){
         
          queue.add(cur);
      }
      
  }
 }
//  System.out.println("numcourse:"+numCourses);
 return numCourses==0; 

 }
}