# 207. 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?
Example 1:
Input: 2, [[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: 2, [[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.
Note:
- 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.
# Solution
Approach 1: the problem is equivalent to detecting cycles in directed graph -- linearlization problem. The first algorithm to solve is by DFS.
Approach 2: the second algorithm to solve the linearlization problem is BFS -- record the indegrees of each node, peel off layers of nodes that has indegree == 0.
# Code (Python)
Approach 1:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# idea: DFS, and mark nodes as in progress while searching in depth
edges = {course: [] for course in range(numCourses)}
# edges flow from advanced courses to prereq
for course, prereq in prerequisites:
edges[course].append(prereq)
# -1: not visited, 1: visited, 0: visiting
visited = [-1] * numCourses
for course in range(numCourses):
if not self._search(course, edges, visited):
return False
return True
def _search(self, node, edges, visited):
if visited[node] == 1:
return True
if visited[node] == 0: # found a cycle!
return False
visited[node] = 0
for neighbor in edges[node]:
if not self._search(neighbor, edges, visited):
return False
visited[node] = 1
return True
Approach 2:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# idea: record the indegrees of each node, peel off layers of nodes that has indegree == 0
edges = {course: [] for course in range(numCourses)}
indegree = {course: 0 for course in range(numCourses)}
layer = set([course for course in range(numCourses)]) # nodes with indegree == 0
# edges flow from prereq to advanced courses
for course, prereq in prerequisites:
edges[prereq].append(course)
indegree[course] += 1
if course in layer:
layer.remove(course)
num_visited = 0
layer = deque(layer)
while layer:
node = layer.popleft()
num_visited += 1
for neighbor in edges[node]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
layer.append(neighbor)
if num_visited == numCourses:
return True
return False
# Code (C++)
Approach 1:
// DFS.
class Solution {
private:
unordered_map<int,vector<int>> neighbors;
vector<bool> visitedPerm;
vector<bool> visitedTemp;
vector<bool> cycling;
bool canFinishCourse(int course) {
if (visitedPerm[course])
return !cycling[course];
if (visitedTemp[course])
return false;
visitedTemp[course] = true;
for (auto v : neighbors[course])
{
if (!canFinishCourse(v))
{
cycling[course] = true;
break;
}
}
visitedTemp[course] = false;
visitedPerm[course] = true;
return !cycling[course];
}
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
for (auto pair : prerequisites)
{
neighbors[pair[0]].push_back(pair[1]);
}
visitedPerm = vector<bool>(numCourses, false);
visitedTemp = vector<bool>(numCourses, false);
cycling = vector<bool>(numCourses, false);
for (int i = 0; i < numCourses; ++i)
{
if (!canFinishCourse(i))
return false;
}
return true;
}
};
Approach 2:
// BFS.
class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
unordered_map<int,int> indegree;
unordered_map<int,vector<int>> edge;
for (int i = 0; i < numCourses; ++i)
{
indegree[i] = 0;
}
for (auto it : prerequisites)
{
int curr = it.first;
int prev = it.second;
indegree[curr]++;
edge[prev].push_back(curr);
}
while (!empty(indegree))
{
unordered_map<int,int>::iterator it;
for (it = indegree.begin(); it != indegree.end(); ++it)
{
if (it->second == 0)
break;
}
if (it == indegree.end())
return false;
int curr = it->first;
indegree.erase(it);
for (auto prev : edge[curr])
{
indegree[prev]--;
}
}
return true;
}
};