LeetCode刷题实战207：课程表
共 3512字，需浏览 8分钟
·
2021-03-14 14:05
For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.
题意
示例
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
解题
class Solution
{
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
{
if (prerequisites.empty()) return true;
map<int, vector<int>> adjcent;
vector<int> indegree(numCourses, 0);
queue<int> q;
int count = 0;
for (auto& course : prerequisites)
{
adjcent[course[1]].push_back(course[0]);
++indegree[course[0]];
}
for (int i = 0; i < numCourses; i++) if (!indegree[i]) q.push(i);
while (q.size())
{
auto cur = q.front();
q.pop();
++count;
for (auto first : adjcent[cur])
{
--indegree[first];
if (!indegree[first]) q.push(first);
}
}
return count == numCourses;
}
};