这道题是典型的有向无环图,注意数据存储的是【当前课:先修课】,所以当我们用一个字典来存的时候,是以【先修课:后续课】存储的
用一个数组来存储每门课先修课的数量,也就是每个节点的入度indegreee
这样存储数据的好处是,每当完成一门先修课的时候,说明当前课的先修课完成了一门,对应的节点入度-1,当入度减少到0时,说明全部的先修课已经上完,可以上当前这门课了。
通过一个队列,将每次入度为0 的节点加入,然后通过字典,找到需要学习这门先修课的后续课,对应的节点入度-1。
最后结果,就是判断是否所有的节点入度都是0,也就是完成所有课程,如果有一个节点不是的话,说明存在环,无法完成。
题目
图解
207code
210题目
这道题相比于之前,就是要返回课程的顺序。用一个数组,来存储队列弹出的顺序即可。
210code