题目描述
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?
Example1:
Input: 2, [[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.
Example1:
Input: 2, [[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.
Note:
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.
解题思路
- 首先是有向图的表示
- 我们定义二维数组 graph 来表示这个有向图，一维数组 in 来表示每个顶点的入度。我们开始先根据输入来建立这个有向图，并将入度数组也初始化好。
- 然后我们定义一个 queue 变量，将所有入度为0的点放入队列中，
- 然后开始遍历队列，从 graph 里遍历其连接的点，每到达一个新节点，将其入度减一，如果此时该点入度为0，则放入队列末尾。直到遍历完队列中所有的值，若此时还有节点的入度不为0，则说明环存在，返回 false，反之则返回 true。
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses, vector<int>());
vector<int> in(numCourses);
for(auto & a : prerequisites){
graph[a[1]].push_back(a[0]); // a[0]指向a[1], a[1]的入度累加
in[a[0]]++;
}
/*
[2, 1], [3, 1], [4,2], [4,3], [5,4]
graph = [
2, 3, // 以1为出度指向2，3
4, // 以2为出度指向4
4, // 以3为出度指向4
5 // 以4为出度指向5
]
*/
queue<int> q;
for(int i = 0; i < numCourses; i++){
if(in[i] == 0){
q.push(i); // 把1给push进去
}
}
while(!q.empty()){
int t = q.front();
q.pop();
for(auto a : graph[t]){ // graph[1] 实际元素为 以1为出度，指向 2，3
--in[a]; // 2, 3 -- ,看是否为0
if(in[a] == 0){
q.push(a);
}
}
}
for(int i = 0; i < numCourses; i++){
if(in[i] != 0){
return false;
}
}
return true;
}
};
