P124. 课程安排

leetcode 207 lintcode 615 回溯 拓扑排序 DFS BFS 讨论

温馨提示:您没有权限查看当前视频。 立即购买观看视频

描述

这个题目说的是,你有 n 门课要上,课程编号从 0 到 n-1。在上某些课之前你需要先上另外一些课程,这种依赖关系可以用一个数对来表示。比如 (0,1) 数对表示在上课程 0 之前,你需要先上课程 1。现在给你 n 门课以及它们之间的依赖关系,你要判断是否有可能上完所有课程。

比如说,给你的课程数量 n 等于 5:

n = 5

课程之间的依赖关系是:

(1, 0)
(3, 0)
(3, 1)
(2, 1)
(2, 3)
(4, 2)
(4, 3)

我们只要按照 0, 1, 3, 2, 4 的顺序来排课,就可以在满足依赖关系的条件下完成这 5 门课。因此返回 true。

提示:上述依赖关系可以转成以下有向图

 0 ---> 3 ---> 4
  \    ^ \    ^
   \  /   \  /
    v/     v/
    1 ---> 2

关于 AlgoCasts

AlgoCasts 旨在用心做好每一个算法讲解视频。每个视频包含两个部分:题目的剖析讲解以及编码,力求在讲解清楚到位的基础上,尽可能地保持视频精简短小,让大家可以在碎片时间里进行学习,并收获这些算法题背后的思想与乐趣。