207. 课程表
一句话套路拓扑排序判环(Kahn / DFS 三色)
题目描述
你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai 则 必须 先学习课程 bi 。
- 例如,先修课程对
[0, 1]表示:想要学习课程0,你需要先完成课程1。
请你判断是否可能完成所有课程的学习?如果可以,返回 true ;否则,返回 false 。
示例 1:
输入:numCourses = 2, prerequisites = [[1,0]] 输出:true 解释:总共有 2 门课程。学习课程 1 之前,你需要完成课程 0 。这是可能的。
示例 2:
输入:numCourses = 2, prerequisites = [[1,0],[0,1]] 输出:false 解释:总共有 2 门课程。学习课程 1 之前,你需要先完成课程 0 ;并且学习课程 0 之前,你还应先完成课程 1 。这是不可能的。
提示:
1 <= numCourses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCoursesprerequisites[i]中的所有课程对 互不相同
思路
时间
O(n+E)空间
O(n+E)思路
拓扑排序(Kahn)。先修关系建边 pre->cur,统计入度;
每次取出入度为 0 的课。若能取完 n 门 -> 无环,否则存在环。
「环」就是有门课程间接要求自己先修完自己。
另解
DFS 三色标记(白/灰/黑),遇到灰色结点即成环 —— Q210 输出方案时更顺手。
求「具体选课顺序」见 Q210,只要把出队顺序记下来。
图解
矩阵(来自本仓库测试数据,红色格子 = 0)
C++17 题解
namespace lc0207 {
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> g(numCourses);
vector<int> indeg(numCourses, 0);
for (const auto& e : prerequisites) { // e = [课程, 先修]
g[e[1]].push_back(e[0]);
++indeg[e[0]];
}
queue<int> q;
for (int i = 0; i < numCourses; ++i)
if (indeg[i] == 0) q.push(i);
int done = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
++done;
for (int v : g[u])
if (--indeg[v] == 0) q.push(v);
}
return done == numCourses;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0207::Solution s;
vector<vector<int>> a{{1, 0}};
CHECK_TRUE(s.canFinish(2, a));
vector<vector<int>> b{{1, 0}, {0, 1}}; // 0<->1 互为先修
CHECK_FALSE(s.canFinish(2, b));
vector<vector<int>> c{{1, 0}, {2, 1}, {3, 2}, {2, 3}}; // 2-3-2 小环
CHECK_FALSE(s.canFinish(4, c));
vector<vector<int>> d{};
CHECK_TRUE(s.canFinish(1, d)); // 没有先修关系