[LeetCode] Course Schedule

There are a total ofncourses you have to take, labeled from0ton – 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair:[0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

解题思路：

这道题可以转换成判断一个有向图是否有环，，若有环，则不能完成，否则能完成。现将课程表示成一个有向图，用邻接表来存储。然后通过DSF来遍历图，若存在一个节点被访问了两次，则表明有环。

注意到这个图可能不是全连通图，所以，需要将每个节点作为开始节点来验证。为了减少遍历次数，用数组mark来记录以某个节点起始的节点进行深度遍历是否有环。下面是代码：

class Solution {public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {int len=prerequisites.size();if(len==0){return true;}vector<vector<int>> graph(numCourses, vector<int>()); //邻接表表示的图for(int i=0; i<len; i++){graph[prerequisites[i][0]].push_back(prerequisites[i][1]);}bool visit[numCourses]; //是否已经访问过memset(visit, 0, numCourses * sizeof(bool));bool mark[numCourses]; //是否已经验证过该节点memset(mark, 0, numCourses * sizeof(bool));for(int i=0; i<numCourses; i++){if(DFSHasCircle(graph, visit, mark, i)){return false;}}return true;}//判断是否有环，思路为若存在一个节点访问了2次，则表明有环bool DFSHasCircle(vector<vector<int>>& graph, bool* visit, bool* mark, int current){if(visit[current]){return true;}if(mark[current]){return false;}visit[current] = true;//标记已经访问过for(int i=0; i<graph[current].size(); i++){if(DFSHasCircle(graph, visit, mark, graph[current][i])){return true;}}mark[current] = true;//表示以该顶点开始的可达的所有节点构成的子图均没有环visit[current] = false;//去掉已经访问过的标记return false;}};

别小看任何人，越不起眼的人。往往会做些让人想不到的事。