1、题目描述

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。

可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

说明:

• 输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
• 你可以假定输入的先决条件中没有重复的边。

2、示例

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

3、题解
解法一：

基本思想：拓扑排序，给定一个包含n个节点的有向图G，给出它的节点编号的一种排列，如果满足：对于图G中的任意一条有向边(u,v)，u在排列中都出现在v的前面，称该排列是图G的拓扑排序。

基本思想：广度优先搜索

• 借助一个队列queue，将所有入度为0的节点入队
• 当queue非空时，依次将队首节点cur出队同时加入res，执行numCourses--，并将cur的所有后继节点的入度 - 1，如果后继节点的入度为0则也入队。
• 若整个课程安排图是有向无环图，则所有节点一定都入队并出队过，最后numCourses = 0，即完成拓扑排序返回res。
• 若课程安排图中存在环路，一定有节点的入度始终不为0，最后numCourses > 0，即不能完成拓扑排序返回空。

解法二：

基本思想：深度优先搜索，判断图中是否有环的同时拓扑排序保存至res。
计算图中节点的入度，从入度为0的节点开始深度优先搜索，搜索到最后一个节点依次递归调用节点返回保存至res
借助一个标志列表flags，用于判断每个节点i的状态：

• 未被 DFS 访问：i=0；
• 已被其他节点启动的 DFS 访问：i=-1；
• 已被当前节点启动的 DFS 访问：i=1。

#include<iostream>
#include<vector>
#include<algorithm>
#include<deque>
#include<map>
using namespace std;
class Solution {
public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {//基本思想：拓扑排序，给定一个包含n个节点的有向图G，给出它的节点编号的一种排列，如果满足：//对于图G中的任意一条有向边(u,v)，u在排列中都出现在v的前面，称该排列是图G的拓扑排序。//基本思想：广度优先搜索//借助一个队列queue，将所有入度为0的节点入队//当queue非空时，依次将队首节点cur出队同时加入res，执行numCourses--，并将cur的所有后继节点的入度 - 1，如果后继节点的入度为0则也入队。//若整个课程安排图是有向无环图，则所有节点一定都入队并出队过，最后numCourses = 0，即完成拓扑排序返回res。//若课程安排图中存在环路，一定有节点的入度始终不为0，最后numCourses > 0，即不能完成拓扑排序返回空。vector<int> res;deque<int> queue;multimap<int, int> HashMap;vector<int> inDegree(numCourses, 0);int cur;for (int i = 0; i < prerequisites.size(); i++){inDegree[prerequisites[i][1]]++;HashMap.insert({ prerequisites[i][0] ,prerequisites[i][1] });}for (int i = 0; i < numCourses; i++){if (inDegree[i] == 0)queue.push_front(i);}while (!queue.empty()){cur = queue.back();res.push_back(cur);queue.pop_back();numCourses--;int cnt = HashMap.count(cur);auto iter = HashMap.find(cur);while (cnt--){inDegree[iter->second]--;if (inDegree[iter->second] == 0)queue.push_front(iter->second);iter++;}}reverse(res.begin(), res.end());return (numCourses == 0) ? res : vector<int>{};}
};
class Solution1 {
public:multimap<int, int> HashMap;    //保存图中节点关系vector<int> res;    //最后返回的拓扑排序vector<int> inDegree;    //计算节点的入度vector<int> flags;    //标记每个节点i的状态vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {//基本思想：深度优先搜索，判断图中是否有环的同时拓扑排序保存至res。//计算图中节点的入度，从入度为0的节点开始深度优先搜索，搜索到最后一个节点依次递归调用节点返回保存至res//借助一个标志列表flags，用于判断每个节点i的状态：//未被 DFS 访问：i=0；//已被其他节点启动的 DFS 访问：i=-1；//已被当前节点启动的 DFS 访问：i=1。for (int i = 0; i < numCourses; i++){inDegree.push_back(0);flags.push_back(0);}//计算所有节点的入度，并建立HashMap保存节点关系方便快速查找当前节点的后继节点for (int i = 0; i < prerequisites.size(); i++){inDegree[prerequisites[i][1]]++;HashMap.insert({ prerequisites[i][0],prerequisites[i][1] });}for (int i = 0; i < numCourses; i++){if (inDegree[i] == 0){if (dfs(i) == false)return {};}}return (res.size() == numCourses) ? res : vector<int>();}bool dfs(int cur){if (flags[cur] == -1)return true;if (flags[cur] == 1)return false;flags[cur] = 1;int cnt = HashMap.count(cur);auto iter = HashMap.find(cur);while (cnt--){if (dfs(iter->second) == false)return false;iter++;}res.push_back(cur);flags[cur] = -1;return true;}
};
int main()
{Solution1 solute;int numCourses = 3;vector<vector<int>> prerequisites = { {1,0},{2,0 } };vector<int> res = solute.findOrder(numCourses, prerequisites);for_each(res.begin(), res.end(), [](const auto v) {cout << v << endl; });return 0;
}