题目:
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
代码:
class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
if(prerequisites.size() < 1 || numCourses < 1)
return true;
vector<vector<int>> graph(numCourses);
vector<int> indegree(numCourses);
for(int i = 0; i<prerequisites.size(); i++)
{
pair<int, int> cur_pair = prerequisites[i];
if(cur_pair.first == cur_pair.second)
return false;
graph[cur_pair.second].push_back(cur_pair.first);
indegree[cur_pair.first]++;
}
int count = 0;
queue<int> q;
for(int i = 0; i<numCourses; i++)
{
if(indegree[i] == 0)
q.push(i);
}
while(!q.empty())
{
int cur = q.front();
count++;
for(auto v : graph[cur])
{
indegree[v]--;
if(indegree[v] == 0)
q.push(v);
}
q.pop();
}
return count == numCourses;
}
};
解法效率优于100.00%~!^0^