LeetCode 207 课程表
LeetCode 207 课程表
LeetCode第207题 课程表
一、题目描述
课程表 你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
示例 1
输入: 2, [[1,0]] 输出: true 解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
示例 2
输入: 2, [[1,0],[0,1]] 输出: false 解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
提示
- 输入的先决条件是由 边缘列表 表示的图形，而不是 邻接矩阵 。详情请参见图的表示法。
- 你可以假定输入的先决条件中没有重复的边。
- 1 <= numCourses <= 10^5
通过次数45,215 提交次数87,276
二、个人思路
题目到手后，发现只要求输出是否有可行方案，并不要求输出具体方案，那么本质上就是判断这个有向图是否存在环路。 如果成环，必然没有可行方案。如果无环，必然有可行方案。 那么这道题就等价于：有向图中，环路的存在性判断问题 。 这就涉及到了图的知识。先上结论，使用DFS对图进行搜索，存在树边，前向边(从祖宗节点指向子孙节点)、后向边(从子孙节点指向祖宗节点)以及横向边(从正在访问的兄弟节点指向非祖孙关系的死节点)。可以证明，后向边的存在与否等价于环的存在与否，所以只要判断是否存在后向边即可。 如何判断是否存在后向边呢？这个可以直接上DFS进行判断。如果当前正在进行扩展的扩展节点遇到了一个活结点，那么就意味着这是一个后向边；如果遇到了死节点，则意味着是横向边或前向边；如果遇到了未访问的节点，则意味着这是一条树边。且如果遇到死节点我们可以完全不必理会，直接略过。 最后将形成一个DFS搜索森林，如果森林中的每棵树都无环，则图无环。（反证法：假设存在树与树之间的环，那么树A应该能沿着环直接搜索到树B，从而A、B为1颗树，不会分为两棵树。故逆否命题：如果是两棵树，则一定不存在两棵树之间的环）
下面是C++代码：
class Solution {
public:
// 先将边缘列表转为邻接表，便于DFS搜索
void initGraph(vector<vector<int>>& prerequisites, list<int>* graph) {
int before, after;
for (int i = 0; i < prerequisites.size(); i++) {
before = prerequisites[i][1];
after = prerequisites[i][0];
(*(graph + before)).push_back(after);
}
}
// 递归的使用DFS判断有没有环路（后向边）
bool hasCycle(list<int>* graph, int v, int* color){
int num = (int)graph[v].size();
int next;
for (int i = 0; i < num; i++) {
next = graph[v].front();
graph[v].pop_front();
if(color[next] == 1) // 后向边，有环路
return true;
else if(color[next] == 0) // 没访问过，标为灰色
color[next] = 1;
else // 已经访问过的横向边，不再拓展
continue;
if(hasCycle(graph, next, color))
return true;
}
color[v] = 2;
return false;
}
// 对图中每个点都进行DFS，最终遍历得到DFS森林
// 如果整个森林都没有环，那么该图就必然无环。
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
if(prerequisites.size() == 0) return true;
list<int> graph[numCourses]; // 邻接表，大小为numCourses
int color[numCourses]; // 用于记录顶点是否访问过的数组
for (int i = 0; i < numCourses; i++) {
color[i] = 0;
}
initGraph(prerequisites, graph); // 将边缘列表转换为邻接表
for (int i = 0; i < numCourses; i++) {
if(color[i] == 0) {
color[i] = 1;
if(hasCycle(graph, i, color))
return false;
}
}
return true;
}
};三、官方题解
详情请移步LeetCode。
腾讯云开发者
