# 207. Course Schedule

There are a total ofncourses you have to take, labeled from0ton - 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 prerequisitepairs, 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.

Thoughts: equivalent to cycle detection problem in topological sort (Kahn's algorithm vs DFS)

Code (Kahn's algorithm)

class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
// make graph outwards
vector<unordered_set<int>> g(numCourses);
vector<int> ind (numCourses, 0);

for(auto p : prerequisites){
g[p.second].insert(p.first);
}
// record in-degrees for each node
for(auto p: prerequisites){
ind[p.first]++;
}

for(int i = 0 ; i < numCourses; i++){
int j = 0;
for(; j < numCourses; j++){
if(!ind[j]) break;
}
if(j== numCourses) return false;
ind[j]--;
for(int neigh: g[j]){
ind[neigh]--;
}
}

return true;
}

};

Code (DFS)

class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<unordered_set<int>> graph = make_graph(numCourses, prerequisites);
vector<bool> onpath(numCourses, false), visited(numCourses, false);
for (int i = 0; i < numCourses; i++)
if (!visited[i] && dfs_cycle(graph, i, onpath, visited))
return false;
return true;
}
private:
vector<unordered_set<int>> make_graph(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<unordered_set<int>> graph(numCourses);
for (auto pre : prerequisites)
graph[pre.second].insert(pre.first);
return graph;
}
bool dfs_cycle(vector<unordered_set<int>>& graph, int node, vector<bool>& onpath, vector<bool>& visited) {
onpath[node] = visited[node] = true;
for (int neigh : graph[node])
// current node and its child nodes
if (onpath[neigh] || dfs_cycle(graph, neigh, onpath, visited))
return true;
// no neightbor case: leaf node, reset the onpath value so that this node can be re-visit
return onpath[node] = false;
}
};

Special Thanks to jianchaolifighter's solution for referenece