[每日一题]207. Course Schedule

There are a total of n courses you have to take, label...



There are a total of n courses you have to take, labeled from 

0

 to 

n - 1

.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: 

[0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

分析

选课是一道应用拓扑排序的经典的题。如下是群里关于这道题的套路







解题

@TK 提供了关于dfs的python版本



dfs版本的基本思路是

1. 使用邻接链表构造一张图，具体是hash实现的。 key 表示节点的值，value表示从它出去的边的另一个节点；
2. 使用dfs深度遍历所有的节点，并保存路径 上面的代码的路径是vis 保存的，vis对应的下标表示的是节点，vis的值为-1时，表示已经访问过改节点，vis为1时，表示没有访问过该节点
3. 判断是否存在环路，如果由则返回false

我参考上面的代码写了一个Ruby版本





区别是 我用的path 来保存路径，所以时间上应该有损耗。

@zer0 提供了一个拓扑排序的版本



拓扑排序的思路上面已经有说明。以上代码的思路是：

1. 用zeroInDegree来保存所有节点的入度的值 比如 节点1 的入度为2，那么体现在zeroInDegree中的结果是 zeroInDegree[1] = 2 所以，当某些点的值是0的时候，就表明该节点的入度是 0
2. 使用队列保存入度为0的节点
3. 在while循环中，我们不断的减去入度为0 的节点的边，并且同步更新zeroInDegree变量，发现zeroInDegree中的值为0 则加入队列
4. 最后比较 zeroInDegree 中的0的节点的数量与节点数量的大小

我对应的写了一个Ruby版本



@Harry何朝阳 提供了一个BFS的Java版本，思路跟上面差不多。





总结

1. 与图相关的问题的首要条件是构造一个图，然后使用dfs或者bfs解题。这个题目还不算太难，因为图是显性的，不需要我们自己的构造状态。有些题目比较难，因为图是隐性的。
2. dfs对应的数据结构是 stack
3. bfs对应的数据结构是 queue

“每日一题”群是一个一起刷leetcode的群。我们每天早上会发一道算法题，每天晚上一起讨论解法和套路。通过讨论和分析，一起寻找解决方案，一起提高算法水平。欢迎能坚持每天刷题的朋友加入！

想加群的朋友请加我的微信: fw_xhde

    关注 一个技术人员的胡言乱语