[LeetCode] Course Schedule
There are a total of n courses you have to take, labeled from 0 to n - 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;
}
};
0 条评论