leetcode207. 课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

思路：拓扑排序
1、创建一个领接表存放所有课程之间的学习关系，所以我们开一个二维数组g存放每门课和它的后继课程；创建一个大小为numCourses的一维数组inDrgree 存放所有课程的先修课程（入度）。 最开始先遍历prerequisities数组，由于prerequisities数组中给的关系是先给后继课程，再给前驱课程，所以存放到g数组的时候要注意一下顺序，前驱课程在前， 后继课程在后。
2、遍历存放所有点之间的依赖关系的数组（这题是prerequisities数组），统计所有入度为0的节点，即没有任何先修课程的课程。
3、有一个队列存放所有的点（入队顺序表示学习课程的顺序），将所有入度为0的节点入队。 然后进行BFS，不断取出队列中的队头元素，并且更新这个点的所有后继节点（这里队头元素是所有入度为0的节点，表示已经学习过的课程， 则这门课的所有后继课程的先修课程数量减一，也就是学了一门先修课程），然后判断减一之后，后继课程们是否已经没有了先修课程（入度是否为0）， 如果入度为0，就把这门课加入到队列中。当然，每取出一门课程，我们都有一个计数变量cnt加一，表示已经修过多少门课程。
4、重复第（2）步，直到队列为空，这时判断一下修过的课程数量cnt是否和课程总数numCourses，如果是，说明存在一种拓扑序列，可以学习完所有课程。 如果不相等，说明不存在。

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<vector<int>> adj(numCourses);vector<int> indegree(numCourses, 0);//每个课程的入度for (auto courseEdge : prerequisites) //边数组转成邻接表{adj[courseEdge[1]].push_back(courseEdge[0]);//a b代表b->a的边indegree[courseEdge[0]]++;//a的入度+1}queue<int> q;//辅助队列int res = 0;for (int course = 0; course < numCourses; course++)if (indegree[course] == 0)q.push(course);//入度为0的课程入队列while (!q.empty())//继续拓扑排序{int cur = q.front();//当前课程q.pop();res++;vector<int>  courseArr = adj[cur];//后修课程for (auto postCourse : courseArr)//遍历每个后修课程{indegree[postCourse]--;//删除该边 即后修课程的入度-1 因为当前节点唯一访问 所以不需要删除邻接表if (indegree[postCourse] == 0)//删除边后 该节点的入度为0且未在拓扑排序中q.push(postCourse);//入队列}}return res == numCourses ? true : false;
}int main() {vector<vector<int> > cours{ {1,0} };int n = 2;bool res = canFinish(n, cours);cout << boolalpha << res << endl;	return 0;
}