问题描述

  1. 给定课程总量以及他们的先决条件，请判断是否可能完成所有课程的学习。
  2. https://leetcode-cn.com/problems/course-schedule/

思路

  1. 死脑筋啊，题目说先决条件是边缘列表而不是邻接矩阵，我就觉得没办法做了？就不能做个转换吗！转成邻接矩阵或者邻接链表就可以了！这就是经典的空间换时间啊。
  2. 邻接链表不知道怎么写？List<List>，用一个嵌套的ArrayList就搞定了！
  3. 拓扑排序怎么搞？起始就是统计一下入度，然后从入度为0的节点开始广度优先遍历就可以了！
  4. 深度优先遍历的思路：用深度优先遍历判断每一个课程能否成功完成，采用深度优先遍历时，需要有一个flags数组来判断当前课程状态，如果是-1，表明该课程可以被成功完成，如果是1，则表明发现循环。
  5. 广度优先遍历是向前看，或者说从前往后看，如果一个课程没有前置课程或者前置课程都被成功完成了，那么该课程一定可以成功完成；时间复杂度是O(N*M)
  6. 深度优先遍历是往后看，往后一直走，看是否会有圈发生。时间复杂度O(N*M)