解题思路:
- 如题目所示,先修课程对 [0, 1] 表示:想要学习课程 0 ,你需要先完成课程 1 。实际上可以想象为有一个值为1的结点指向值为0的结点,而且每一个可以指向的结点数量并不固定,所以就是个有向图,而要想判断是否能够完成,实际上对于图来说如果存在环那么就意味着存在两个结点互相指向(互相需要),所以如果存在环那么一定无法学完所有课程
- 注意:
1.如何将题目所给参数转化为抽象的图结构
2.如何进行深度优先搜索
3.如何判断是否存在环结构
class Solution {
// 本题思路是将题目转化未有向图结构,利用深度优先搜索来判断是否存在环,如果图中存在环那么就不可能完成所有课程的学习
private:
// 存储有向图
vector<vector<int>>edges;
//存储结点状态0=未搜素,1=正在搜索,2=搜索完成
vector<int>visited;
// 假设不存在环
bool valid = true;
public:
void dfs(int u){
visited[u]=1;
for(int v:edges[u]){
if(visited[v]==0){
dfs(v);
if(!valid)return;
}
// 在进行深度优先搜索时,搜索到了一个已经正在搜索的,说明形成了环
else if(visited[v]==1){
valid = false;
return;
}
}
// 搜索结束后要将该结点的标志进行修改
visited[u] = 2;
}
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
edges.resize(numCourses);
visited.resize(numCourses);
// 转换成有向图存储
for(auto temp:prerequisites){
edges[temp[1]].push_back(temp[0]);
}
for(int i = 0;i<numCourses && valid;++i){
if(visited[i]==0){
dfs(i);
}
}
return valid;
}
};