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
排课表问题，一看就是拓扑排序的题。
之前介绍过，拓扑排序有两种解法，一种是类似BFS的Kahn算法，另一种是DFS算法，具体可以参考维基百科的伪代码。
解法1：Kahn算法。基本思想，首先把所有入度为0的点放到集合S中（表示这些课没有先修课程，可以首先完成），然后不断从S中取点x，把x指向的所有的点y的边(x,y)删掉，如果删掉之后，y的入度也变为0了，把y也加入到S中。当S为空时，如果图中还有边没删掉，说明形成环了，否则是一个DAG。
想象一下图中的一个环，如同时有边(x,y)和(y,x)，则x和y因为都有入度，说明都不可能加入到集合S中，所以这两条边永远都删不掉。
Kahn的算法很好理解，代码类似于BFS，如下：
class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int> >& prerequisites)
{
int numEdges = prerequisites.size();
vector<set<int> > pre(numCourses, set<int>()), next(numCourses, set<int>());
for (const auto& p : prerequisites) {
pre[p.first].insert(p.second);
next[p.second].insert(p.first);
}
queue<int> Q;
for (int i = 0; i < numCourses; ++i) {
if (pre[i].size() == 0)
Q.push(i);
}
while (!Q.empty()) {
int node = Q.front();
Q.pop();
for (const auto& n : next[node]) {
pre[n].erase(node);
–numEdges;
if (pre[n].size() == 0)
Q.push(n);
}
}
return numEdges == 0;
}
};本代码提交AC，用时15MS。
解法2：DFS算法。还可以用DFS求解，基本思想是，维护两个访问标记数组，visited[i]表示全局是否被访问数组，相当于维基百科中的permanently标记，onpath[i]表示当前DFS路径是否被访问数组，相当于维基百科中的temporarily标记。
对于所有visited[i]没访问的点i，我们DFS它。把从i开始DFS到的点标记为onpath[j]，如果在DFS的过程中访问到了onpath[k]被标记过的点，说明这条路形成了环，返回false，不是DAG。否则，如果visited[node]==1，说明node是DFS之前的点时被访问过，而之前的DFS返回了true，说明从node DFS的结果是不会形成环的，可以直接返回true。否则如果visited[node]==0，我们从node继续DFS，具体步骤是，首先标记onpath[node]=1，然后把node指向的所有点都DFS一遍，如果都没发现换，则永久标记visited[node]=1，说明从node这个点DFS是没问题的，不会形成环的；同时复位onpath[node]=0，以便下次DFS使用。
完整代码如下，实现方法完全参考维基百科中的DFS版本。
class Solution {
private:
bool dfs(vector<int>& visited, vector<int>& onpath, vector<vector<int> >& graph, int node)
{
if (onpath[node] == 1)
return false;
if (visited[node] == 0) {
onpath[node] = 1;
for (int i = 0; i < graph.size(); ++i) {
if (graph[node][i] == 1) {
if (!dfs(visited, onpath, graph, i))
return false;
}
}
visited[node] = 1;
onpath[node] = 0;
return true;
}
return true;
}
public:
bool canFinish(int numCourses, vector<pair<int, int> >& prerequisites)
{
vector<vector<int> > graph(numCourses, vector<int>(numCourses, 0));
for (const auto& p : prerequisites)
graph[p.second][p.first] = 1;
vector<int> visited(numCourses, 0), onpath(numCourses, 0); // visited==permanently; onpath=temporarily
for (int i = 0; i < numCourses; ++i) {
if (visited[i] == 0) {
if (!dfs(visited, onpath, graph, i))
return false;
}
}
return true;
}
};本代码提交AC，用时62MS，比Kahn慢好多。
二刷。上述解法也太复杂了，直接循环把入度为0的删掉就行了，完整代码如下：
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses, vector<int>(numCourses, 0));
vector<int> indegree(numCourses, 0);
for (int i = 0; i < prerequisites.size(); ++i) {
graph[prerequisites[i][1]][prerequisites[i][0]] = 1;
++indegree[prerequisites[i][0]];
}
int finish = 0;
while (true) {
bool found = false;
for (int i = 0; i < numCourses; ++i) {
if (indegree[i] == 0) {
--indegree[i];
++finish;
found = true;
for (int j = 0; j < numCourses; ++j) {
if (graph[i][j] == 1) {
graph[i][j] = 0;
--indegree[j];
}
}
}
}
if (!found)break;
}
return finish == numCourses;
}
};本代码提交AC，用时76MS。