课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
算法原理：
本题题意要先搞懂，举个例子：
假设传入的这个数组，以[1,0]来说，它的意思就是要想先修1，就必须先学习0这门课程，依次内推。想这个我们可以画个箭头好理解：0->1 意思就是学1要先学0；
分析到这，我们就可以把这个数组抽象出来：
这个图是不是很熟悉，这不就是我们的有向图吗？
看一下题目问的啥，问能否修完？那这问题的本质不就是给这个图能否拓扑排序，或者问这个图是不是有环.
分析到这，其实就可以动手写代码了，但是我们前言末尾说到过，实现拓扑排序的前提是要建图。我们先打一下理论基础，看如何建图：
首先如何灵活建图的前提我们要合理用我们的容器。
其次要看数据的稠密也就是数据量，我们通常有两种办法：
- 邻接矩阵
- 邻接表
邻接矩阵市面上书籍讲的很多，这里我们采用邻接表的形式。
什么是邻接表呢？
以刚才例子为例，我们把每个位置相连的点都放在一排，所形成的这个表就是邻接表。
可能有人好奇，那我们岂不是要实现一个链表，才能形成上面的对应关系，其实不然，我们用数组就可以模拟代替链表。
接下来我们可以选择合适的容器，也就是代码如何实现，这里我们给出两种：
- vector
我们在vector里嵌套一个vector：
vector<vector<int>> edge;//edge边的意思
为什么二维数组就可以呢？
我们让其下标具有对应关系，咱们得邻接表不就出来了。
- 哈希表
用哈希表来实现邻接表：
unordered_map<int,vector<int>> edge; unordered_map<string,vector<string>> edge;
用哈希来反映映射也是可以的。
代码实现：
class Solution { public: bool canFinish(int n, vector<vector<int>>& prerequisites) { //1.准备工作 unordered_map<int,vector<int>> edge;//邻接表存图 //vector<vector<int>> edge(n); vector<int> in(n);//用来标记入度 //2.建图 for(auto& e:prerequisites) { int a=e[0],b=e[1]; //b->a的一条边 //拿到b的这条边 //把a插入到b的后面 edge[b].push_back(a); //有一条边指向a了，a入度++ in[a]++; } //3.拓扑排序 queue<int> q; //(1)把所有入度为0的点加入到队列中 for(int i=0;i<n;i++) { //入度为0 if(in[i]==0) //加入队列 q.push(i); } //（2）bfs while(q.size()) { int t=q.front(); q.pop(); //拿出点后，要把这个点相连的边删掉 for(int a:edge[t]) { //入度-- in[a]--; //如果入度为0，进入队列 if(in[a]==0) q.push(a); } } //4.判断是否有环 for(int i=0;i<n;i++) { if(in[i]) return false; } return true; } };
课程表 II
现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。
算法原理：
本题跟课程表一模一样，只是返回的结果不一样，本题要返回一个序列，所以我们用一个数组统计一下信息即可。
代码实现：
class Solution { public: vector<int> findOrder(int n, vector<vector<int>>& prerequisites) { //1.准备工作 vector<vector<int>> edge(n);//用来储存图 //unordered_map<int,vector<int>> edge; vector<int> in(n);//用来标记入度 //2.建图 for(auto& e:prerequisites) { int a=e[0],b=e[1]; //b->a的一条边 //把a插入到b的后面 edge[b].push_back(a); // in[a]++; } //3.拓扑排序 queue<int> q; vector<int> ret; //(1)把所有入度为0的点加入到队列中 for(int i=0;i<n;i++) { //入度为0 if(in[i]==0) //加入队列 q.push(i); } //（2）bfs while(q.size()) { int t=q.front(); q.pop(); ret.push_back(t); for(int a:edge[t]) { //入度-- in[a]--; //如果入度为0，进入队列 if(in[a]==0) q.push(a); } } //4.判断是否有环 if(ret.size()==n)return ret; else return {}; } };
总结：
其实用代码建图很简单，对于代码其实也就两三行的事情：
- 准备工作
//数组模拟 vector<vector<int>> edge(n)//n是大小 //哈希表模拟 unordered_map<int,vector<int>> edge; //入度 vector<int> in(n);
- 建图
for(auto& e:prerequisites) { int e[0]=a,e[1]=b; b->a; //找到b这条边 e[b].push_back(a); //有一条边指向了a //a入度++ in[a]++; }
- 拓扑排序
排序就根据前言分析的步骤实现。
