210. Course Schedule II

210. 课程表 II

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

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

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

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

示例 1:

输入: 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] 。

说明:

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

提示:

1. 这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
2. 通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。

3. 拓扑排序也可以通过 BFS 完成。

解法一：

//时间复杂度O(n), 空间复杂度O(n)
class Solution {
public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {vector<int> indegree(numCourses, 0);//入度vector<vector<int>> adjacencyList(numCourses);//邻接表for(auto vec : prerequisites) {indegree[vec[0]]++;//计算每个结点的入度adjacencyList[vec[1]].push_back(vec[0]);//构建邻接表}stack<int> st;for(int i = 0; i < numCourses; i++) if(indegree[i] == 0) st.push(i);//将入度为0的入栈vector<int> res;while(!st.empty()) {int temp = st.top();st.pop();res.push_back(temp);for(int e : adjacencyList[temp]) {indegree[e]--;if(indegree[e] == 0) st.push(e);}numCourses--;}if(numCourses != 0) return {};return res;}
};

解法一：

数组indegree记录了从0至n-1每个结点的入度，adjacencyList是整个图的邻接表。

1. 首先根据前置条件prerequisites对每个结点计算入度indegree[i]，同时构建整个图的邻接表。
2. 使用一个栈（或其他容器，不要求顺序），将每个入度为0的结点入栈。入度为0代表着该结点没有先修课程，说明它可以作为要选上的第一门课。
3. 当栈非空时，持续出栈，将出栈结点对应邻接表中的元素入度减1（同时检查元素入度，如果为0，就入栈），同时将出栈元素追加在res中。每次出栈将numCourses减1。
4. 如果有向图无环，则numCourses最后应该等于0，如果是这样，返回res。否则返回空。

另一种解法，对每个结点进行DFS操作，类似第207题解法一。