上次写了关于拓扑排序的写法，今天这个题就是关于拓扑排序的应用与改进。
第12题：207. Course Schedule
文章大意：课程安排，课程之间有依赖性。给定课程数，和课程之间的依赖，判断课程能否顺利完成。
题目分析：这不就是之前写的拓扑排序能干嘛吗？所以这是一个拓扑排序的问题，所以啊直接开始干。要注意的是，后面给数组中，后面一个表示前驱节点。即[1,0]表示的是0->1.
分析和实现主要见上篇文章：拓扑排序，这里直接贴代码：
class Solution { public: bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { if(numCourses <= 1 ) return true; int len = prerequisites.size(); if(len==1) return true; int degree[numCourses]; memset(degree, 0, sizeof(int)*numCourses); int graph[numCourses][numCourses] = {0}; //二维数组存储邻接矩阵 for(int i=0;i<numCourses;i++){ for(int j=0;j<numCourses;j++){ graph[i][j] = 0; } } for(int i=0;i<len;i++){ graph[prerequisites[i][1]][prerequisites[i][0]] = 1; //建立有向边关系 degree[prerequisites[i][0]]++; //记录每个节点的入度 } int node = 0; while(node < numCourses){ for(node=0;node<numCourses;node++){ if(degree[node]==0){ //选取一个入度为0的节点 degree[node]--; break; } } if(node < numCourses){ for(int i=0;i<numCourses;i++){ //删除该节点的有向边 if(graph[node][i] != 0){ graph[node][i] = 0; degree[i]--; } } } } for(int i=0;i<numCourses;i++){ //若还存在节点的入度大于0，则返回false if(degree[i] > 0) return false; } return true; } };算法比较粗糙，没有做太多的优化处理，所以没想着效果会有多好，提交之后果然。。心态微崩
分析一下代码的话，就是运行时间长，占用空间大，实在是有点糙。
算法优化：
优化从上到下来看，首先就是一个二维数组的初始化，用的一个二重循环，内存写-慢。所以做一个优化，如下：
for(int i=0;i<numCourses;i++){ for(int j=0;j<numCourses;j++){ graph[i][j] = 0; } } // 采用一个单重循环，然后用memset函数，进行内存的初始化。用来替换上面的双重循环赋值初始化 for(int i=0;i<numCourses;i++){ memset(graph[i], 0, sizeof(int)*numCourses); }然后就是关于拓扑排序算法的优化，算法是一个while循环，内含两个平行for循环。目的是找出一个入度为0的节点，并删除所有与它相关（由它作为前驱节点）的有向边。寻找节点的过程，每次都进行了一次完整的for循环，思考能不能直接得到这个节点呢？而且做删除操作的时候，会改变一些节点的入度，这个时候可以产生一些入度为0的节点，如果能够把这些节点存储起来，那么就不用再额外用一个循环来寻找节点了。然后做了以下优化：
queue<int> qu; //用一个队列来存储入度为0的节点 for(int i=0;i<numCourses;i++){ if(degree[i]==0){ qu.push(i); } } int node = 0; int cnt = numCourses; //记录入度为0的节点数 while(!qu.empty()){ //判断是否再没有节点入度为0 cnt--; node = qu.front(); qu.pop(); degree[node]--; //将该节点的入度减少，这里变成了-1 for(int i=0;i<numCourses;i++){ if(graph[node][i] != 0){ //寻找所有的关联有向边 graph[node][i] = 0; degree[i]--; //将后驱节点的入度减少 if(degree[i]==0) qu.push(i); //这时候，如果已经有节点入度为0，则入队列 } } } return (cnt>0?false:true);提交一下：
我太南了qaq.....这个优化之后，效果还是不咋地。想着只有后面一个东西可以优化了，就是二维数组存储图那里，而且这个也使得占用空间过大。确实，当图是稀疏图的时候，用二维数组的方式来存储会造成过大的空间浪费。看了一下前面16ms的推荐写法，发现将二维数组用一个双重vector来替代了，这样确实会大大节省一些不必要的空间，同时在后面寻找关联边的时候很方便了，因为就是一个vector的元素。最终代码如下：
class Solution { public: bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { if(numCourses <= 1 ) return true; int len = prerequisites.size(); if(len==1) return true; int degree[numCourses]; //用来记录节点入度 memset(degree, 0, sizeof(int)*numCourses); vector<vector<int>> graph(numCourses); //采用vector来替换二维数组 for(int i=0;i<len;i++){ //vector[i]表示i节点的所有后驱节点 graph[prerequisites[i][1]].push_back(prerequisites[i][0]); degree[prerequisites[i][0]]++; } queue<int> qu; //队列用来记录入度为0的节点 for(int i=0;i<numCourses;i++){ if(degree[i]==0){ qu.push(i); } } int node = 0; int cnt = numCourses; while(!qu.empty()){ cnt--; node = qu.front(); qu.pop(); degree[node]--; for(int i : graph[node]){ //graph[node]即是表示node的所有后驱节点 degree[i]--; //将后驱节点的入度减少 if(degree[i]==0) qu.push(i); //如果后驱节点的入度为0，则入队列 } } return (cnt>0?false:true); } };最终结果：20ms，咱也不知道，咱也不敢问。
还有前面速度更快地算法，但是与这里算法相差太大，也就没有继续修改了。以上
