现在你总共有 n 门课需要选，记为
0到n-1。在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们:
[0,1]给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？
示例 1:
输入: 2, [[1,0]] 输出: true 解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。示例 2:
输入: 2, [[1,0],[0,1]] 输出: false 解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。说明:
- 输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
- 你可以假定输入的先决条件中没有重复的边。
提示:
- 这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
- 通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
拓扑排序也可以通过 BFS 完成。
解法一：
//时间复杂度O(n+m), 空间复杂度O(n+m), n是结点数, m是边数
class Solution {
public:
bool dfs(const vector<vector<int>>& adjacencyList, int i, vector<int>& flag) {
if(flag[i] == -1) return true;//-1表示被之前的遍历访问过，不用再访问了
if(flag[i] == 1) return false;//有环
flag[i] = 1;//置1说明被当前遍历访问过
for(int next : adjacencyList[i]) {
if(!dfs(adjacencyList, next, flag)) return false;
}
flag[i] = -1;//完成后将1置为-1
return true;
}
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> adjacencyList(numCourses);
for(auto vec : prerequisites) adjacencyList[vec[0]].push_back(vec[1]);//构建邻接表
vector<int> flag(numCourses, 0);
for(int i = 0; i < numCourses; i++) {
if(!dfs(adjacencyList, i, flag)) return false;
}
return true;
}
};解法一：
DFS。数组flag记录了每个结点的状态，-1代表被其它遍历访问过，1代表被当前遍历访问过，0代表未访问过。
为了便于后续的查找，首先根据prerequisites构建邻接表。然后遍历每一个结点，从当前结点开始进行DFS操作，如果遇到环就返回false。
2020/01/09 13:46