HHot 100C++ 图解

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 <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • prerequisites[i] 中的所有课程对 互不相同

思路

时间O(n+E)
空间O(n+E)

思路

拓扑排序(Kahn)。先修关系建边 pre->cur,统计入度;

每次取出入度为 0 的课。若能取完 n 门 -> 无环,否则存在环。

「环」就是有门课程间接要求自己先修完自己。

另解

DFS 三色标记(白/灰/黑),遇到灰色结点即成环 —— Q210 输出方案时更顺手。

求「具体选课顺序」见 Q210,只要把出队顺序记下来。

图解

j0 j1 i0 1 0 i1 2 1 i2 3 2 i3 2 3
矩阵(来自本仓库测试数据,红色格子 = 0)

C++17 题解

src/09_graph.cpp25 行
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;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q207_course_schedule9 行
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));  // 没有先修关系

↑↓ 选择↵ 打开/ 随时唤起