# LeetCode Course Schedule

LeetCode Course Schedule

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?

For example:

`2, [[1,0]]`

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

`2, [[1,0],[0,1]]`

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:

1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
2. You may assume that there are no duplicate edges in the input prerequisites.

Hints:

1. This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
2. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
3. Topological sort could also be done via BFS.

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;
}
};
```

```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;
}
};
```