题目网址 https://leetcode-cn.com/problems/course-schedule/
There are a total of numCourses courses you have to take, labeled from 0 to numCourses-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?
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: 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.
Constraints:
- The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
- You may assume that there are no duplicate edges in the input prerequisites.
1 <= numCourses <= 10^5
思路分析
首先这个题目是一个非常明显的判断有向图是否有环的问题，下面是我用的两种解法
1. DFS
用dfs来处理是需要注意，如果visited数组只有两种状态，即访问过或者未访问过，那么这不足以判断有向图是否有环，因为visited数组中存了三种状态
（1）访问已完成
（2）正在访问
（3）尚未访问
只有当我们访问到标记为状态(2)的节点才说明有有向环，因为如果访问到了标记为状态(2)的节点，则说明在访问此节点的子孙节点时有重新访问了此节点，那么就会形成一个有向环。
代码如下：
class Solution {
public:
vector<vector<int>> graph;
vector<int> visited;
bool ans=true;
void dfs(int i, vector<vector<int>>& graph, vector<int>& visited){
if(ans==false)return;
if(visited[i]==2){
return;
}
if(visited[i]==1){
ans = false;
return;
}
visited[i]=1;
for(auto node:graph[i]){
dfs(node, graph, visited);
}
visited[i]=2;
}
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
graph.resize(numCourses);
visited.resize(numCourses);
for(auto edge:prerequisites){
graph[edge[1]].push_back(edge[0]);
}
for(int i=0;i<numCourses;i++){
if(visited[i]==0){
dfs(i, graph, visited);
if(ans==false)return false;
}
}
return true;
}
};
2. 拓扑排序（BFS）
首先将所有入度为0的节点加入queue，依次删除队列中节点的出度对应的边并把更新过后入度为0的节点加入queue，直到队列为空。最后需要检查在此操作之后是不是所有的节点入度都为0，如果不是则存在环。
代码如下：
class Solution {
public:
vector<vector<int>> graph;
vector<int> indegree;
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
graph.resize(numCourses);
indegree.resize(numCourses);
for(auto edge:prerequisites){
graph[edge[1]].push_back(edge[0]);
indegree[edge[0]]++;
}
queue<int> q;
for(int i=0;i<numCourses;i++){
if(indegree[i]==0)q.push(i);
}
while(!q.empty()){
int front=q.front();
for(auto node:graph[front]){
indegree[node]--;
if(indegree[node]==0)q.push(node);
}
q.pop();
}
for(int i=0;i<numCourses;i++){
if(indegree[i]!=0){
return false;
}
}
return true;
}
};
这题是图的典型题目，需要重视起来！就酱～
