链接
LeetCode题目：https://leetcode.com/problems/course-schedule/
难度：Medium
题目
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?
题目大意是选n门课程，某些课程可能有先修课程，试问能否成功选择全部课程。
分析
这题是一道典型的拓扑排序问题，拓扑排序的定义是：将有向图中的顶点以线性方式进行排序，对于任何连接自顶点u到顶点v的有向边uv，在最后的排序结果中，顶点u总是在顶点v的前面。 典型的实现算法有Kahn算法和基于DFS的算法，Kahn算法相比后者的好处是不需要检测图为DAG，所以我选择了Kahn算法。 做法是维护一个入度为0的点的集合（这里选择了队列），每次从集合中取出一个点n，依次删除从n到m的边，如果删后m的入度为0，则把点m也放入这个集合。最后集合为空而且不存在边时，证明选课成功。时间复杂度是O(V+E)，其中V为边数，E为点数。
代码
class Solution {
public:
bool canFinish(
int numCourses,
vector<pair<int, int>> &prerequisites) {
edgeNum = prerequisites.size();
inDegrees =
vector<int>(numCourses,
0);
for (
int i =
0; i < numCourses; i++) {
edges.push_back(
vector<int>());
}
for (
auto pre:prerequisites) {
edges[pre.second].push_back(pre.first);
inDegrees[pre.first]++;
}
for (
int i =
0; i < inDegrees.size(); i++) {
if (inDegrees[i] ==
0) points.push(i);
}
while (points.size()) {
int n = points.front();
points.pop();
for (
auto m:edges[n]) {
edgeNum--;
inDegrees[m]--;
if (!inDegrees[m]) points.push(m);
}
}
return edgeNum ==
0;
}
private:
int edgeNum;
vector<int> inDegrees;
vector<vector<int>> edges;
queue<int> points;
};
