0210. Course Schedule II
========================
题目信息
--------
:题号: 0210. 课程表 II
:难度: Medium
:主题: 有向图、拓扑排序、顺序构造、环检测
:原题: `LeetCode 0210 `_
:重点: 维护合法拓扑前缀,全部课程出队才返回顺序,遇到环则丢弃部分结果
题目重述
--------
共有 ``numCourses`` 门课程,编号为 ``0`` 到 ``numCourses - 1``。先修关系
``[course, prerequisite]`` 表示必须先完成 ``prerequisite``,才能完成 ``course``。返回任意一个
包含全部课程、且满足每条先修关系的学习顺序;若不存在完整顺序,返回空数组。
``numCourses`` 位于 ``[1, 2000]``,先修关系数量位于 ``[0, numCourses * (numCourses - 1)]``,
关系对合法、互不重复且不存在 ``[x, x]``。合法顺序可能不唯一,返回数组必须恰好包含每门课程一次。
自建示例
--------
一条先修链:
.. code-block:: text
输入:numCourses = 2,prerequisites = [[1,0]]
输出:[0,1]
分支课程可以互换顺序:
.. code-block:: text
输入:numCourses = 4,prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出:[0,1,2,3] 或 [0,2,1,3]
存在环时不能返回剩余可完成课程:
.. code-block:: text
输入:numCourses = 4,prerequisites = [[1,0],[2,1],[0,2]]
输出:[]
C++ 实现
--------
.. code-block:: cpp
#include
#include
#include
class Solution {
public:
std::vector findOrder(int numCourses,
std::vector>& prerequisites) {
return orderByIndegree(numCourses, prerequisites);
}
private:
std::vector orderByIndegree(
int numCourses, const std::vector>& prerequisites) {
std::vector> graph(numCourses);
std::vector indegree(numCourses, 0);
for (const auto& prerequisite : prerequisites) {
int course = prerequisite[0];
int prerequisiteCourse = prerequisite[1];
graph[prerequisiteCourse].push_back(course);
++indegree[course];
}
std::queue ready;
for (int course = 0; course < numCourses; ++course) {
if (indegree[course] == 0) ready.push(course);
}
std::vector order;
while (!ready.empty()) {
int course = ready.front();
ready.pop();
order.push_back(course);
for (int next : graph[course]) {
if (--indegree[next] == 0) ready.push(next);
}
}
if (static_cast(order.size()) != numCourses) return {};
return order;
}
std::vector orderByDfs(
int numCourses, const std::vector>& prerequisites) {
std::vector> graph(numCourses);
for (const auto& prerequisite : prerequisites) {
graph[prerequisite[1]].push_back(prerequisite[0]);
}
std::vector state(numCourses, 0);
std::vector order;
for (int course = 0; course < numCourses; ++course) {
if (state[course] == 0 && hasCycle(course, graph, state, order)) {
return {};
}
}
std::reverse(order.begin(), order.end());
return order;
}
bool hasCycle(int course,
const std::vector>& graph,
std::vector& state,
std::vector& order) {
state[course] = 1;
for (int next : graph[course]) {
if (state[next] == 1) return true;
if (state[next] == 0 && hasCycle(next, graph, state, order)) return true;
}
state[course] = 2;
order.push_back(course);
return false;
}
};
题解
----
返回顺序比判断可行多一个状态
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
只判断能否完成时,答案可以压缩成一个布尔值;本题还要返回每门课程的先后,因此算法必须在
判断无环的同时构造一个顺序。将关系定向为 ``prerequisite -> course`` 后,目标就是构造拓扑序:
每条边的起点出现在终点之前。
枚举排列与安全选择
~~~~~~~~~~~~~~~~~~~~
枚举所有课程排列并逐条验证先修关系是阶乘级搜索。更有用的直接策略是反复寻找当前没有未完成
先修课的课程,并把它追加到输出末尾;这样的课程入度为 0,把它放在当前拓扑前缀之后不会违反
任何边。
若仍有课程却找不到零入度课程,剩余依赖必然形成环。此时已经构造出的前缀可能合法,但它不是
题目要求的“包含全部课程”的答案,必须返回空数组,不能把部分顺序交给调用者。
Kahn 算法直接生成拓扑前缀
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
``orderByIndegree`` 维护邻接表和每门课程的剩余入度:
1. 建立从先修课到后续课的边,并统计后续课入度;
2. 把所有入度为 0 的课程放入队列;
3. 弹出一门课程并追加到 ``order``;
4. 删除它的每条出边,后继入度减一;
5. 后继第一次变为 0 时入队。
每轮的 ``order`` 都是合法拓扑前缀。入度只递减,所以一门课程最多入队一次;当队列为空时,
若 ``order`` 长度小于课程数,剩余图没有可启动节点,必含有环。
状态不变量
~~~~~~~~~~~~
每次从队列取出课程前保持:
* ``indegree[v]`` 等于未进入 ``order`` 的课程指向 ``v`` 的剩余边数;
* 队列中的课程尚未进入 ``order`` 且当前入度为 0;
* ``order`` 中没有重复课程,且已满足其中所有边的先后关系;
* 每条出边只在起点加入 ``order`` 后删除一次。
弹出的课程没有来自未处理课程的入边,可以安全追加;删除它的出边只会减少后继的剩余要求。
某个后继从 1 变为 0 时,恰好说明所有先修课程都已进入前缀,加入队列不会破坏不变量。
状态走读
~~~~~~~~
对菱形依赖 ``0->1、0->2、1->3、2->3``:
.. list-table::
:header-rows: 1
* - 阶段
- ready
- indegree
- order
* - 初始化
- ``[0]``
- ``[0,1,1,2]``
- ``[]``
* - 弹出 0
- ``[1,2]``
- ``[0,0,0,2]``
- ``[0]``
* - 弹出 1
- ``[2]``
- ``[0,0,0,1]``
- ``[0,1]``
* - 弹出 2
- ``[3]``
- ``[0,0,0,0]``
- ``[0,1,2]``
* - 弹出 3
- ``[]``
- ``[0,0,0,0]``
- ``[0,1,2,3]``
若先弹出 2,则得到 ``[0,2,1,3]``,仍然合法;队列选择顺序只影响一个可行答案,不改变拓扑
约束本身。环 ``0->1->2->0`` 初始化时没有零入度课程,``order`` 为空,最后必须丢弃它。
DFS 逆后序作为替代法
~~~~~~~~~~~~~~~~~~~~~~
``orderByDfs`` 使用三种状态:0 未访问,1 在当前递归路径中,2 已完成。沿边访问时遇到状态 1,
说明回到了当前路径祖先,存在环;一个节点所有后继都完成后再把它加入 ``order``,得到的是
逆后序,最后整体反转即为拓扑序。
DFS 适合展示“回边就是环”的结构,但递归栈最坏达到课程数;主入口选择 Kahn,让输出顺序在出队
时直接形成,也避免深递归。两种方法都必须遍历所有课程,不能只从课程 0 开始,因为图可能有
多个分量或孤立课程。
代码分析
~~~~~~~~
建图时 ``prerequisite[1]`` 是边起点,``prerequisite[0]`` 是终点;入度增加在终点。Kahn
每弹出一门课程就把它追加到结果,不需要额外排序;后继入度只在对应边被删除时递减。
最后用 ``order.size()`` 与 ``numCourses`` 比较,而不是只返回当前前缀。数量不足代表有环,
代码返回空数组,避免把部分合法前缀误当成完整答案。DFS 版本则在发现回边时立即返回空,
无环完成后反转后序列表。
复杂度与边界
~~~~~~~~~~~~
设课程数为 ``V``、先修关系数为 ``E``。两种方法都建立并遍历每个顶点和每条边一次,时间复杂度
``O(V + E)``;邻接表、入度或访问状态、队列/递归栈的工作空间为 ``O(V + E)``。返回数组本身
还承载 ``O(V)`` 个课程编号,不能计入常量空间。
没有先修关系时所有课程初始入队,返回包含全部编号的任意顺序;孤立课程与其他分量独立推进。
单门课程直接返回 ``[0]``;自环虽被题目排除,若出现也会使该课程入度不为 0,最终返回空数组。