leetcode：210. 课程表 II

210. 课程表 II
     提示
     中等
     889
     相关企业
     现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。

例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
示例 2：

输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
示例 3：

输入：numCourses = 1, prerequisites = []
输出：[0]

提示：
1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
所有[ai, bi] 互不相同

方法一：深度优先搜索

class Solution {
private:// 存储有向图vector<vector<int>> edges;// 标记每个节点的状态：0=未搜索，1=搜索中，2=已完成vector<int> visited;// 用数组来模拟栈，下标 0 为栈底，n-1 为栈顶vector<int> result;// 判断有向图中是否有环bool valid = true;public:void dfs(int u) {// 将节点标记为「搜索中」visited[u] = 1;// 搜索其相邻节点// 只要发现有环，立刻停止搜索for (int v: edges[u]) {// 如果「未搜索」那么搜索相邻节点if (visited[v] == 0) {dfs(v);if (!valid) {return;}}// 如果「搜索中」说明找到了环else if (visited[v] == 1) {valid = false;return;}}// 将节点标记为「已完成」visited[u] = 2;// 将节点入栈result.push_back(u);}vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {edges.resize(numCourses);visited.resize(numCourses);for (const auto& info: prerequisites) {edges[info[1]].push_back(info[0]);}// 每次挑选一个「未搜索」的节点，开始进行深度优先搜索for (int i = 0; i < numCourses && valid; ++i) {if (!visited[i]) {dfs(i);}}if (!valid) {return {};}// 如果没有环，那么就有拓扑排序// 注意下标 0 为栈底，因此需要将数组反序输出reverse(result.begin(), result.end());return result;}
};

方法二：广度优先搜索

class Solution {
private:// 存储有向图vector<vector<int>> edges;// 存储每个节点的入度vector<int> indeg;// 存储答案vector<int> result;public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {edges.resize(numCourses);indeg.resize(numCourses);for (const auto& info: prerequisites) {edges[info[1]].push_back(info[0]);++indeg[info[0]];}queue<int> q;// 将所有入度为 0 的节点放入队列中for (int i = 0; i < numCourses; ++i) {if (indeg[i] == 0) {q.push(i);}}while (!q.empty()) {// 从队首取出一个节点int u = q.front();q.pop();// 放入答案中result.push_back(u);for (int v: edges[u]) {--indeg[v];// 如果相邻节点 v 的入度为 0，就可以选 v 对应的课程了if (indeg[v] == 0) {q.push(v);}}}if (result.size() != numCourses) {return {};}return result;}
};