207. Course Schedule

  • 31.0%

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?

1
2
3
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.

1
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:

  • 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.

Hints:

  • 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.
  • Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
  • Topological sort could also be done via BFS.

https://discuss.leetcode.com/topic/17273/18-22-lines-c-bfs-dfs-solutions

18-22 lines C++ BFS/DFS Solutions

As suggested by the hints, this problem is equivalent to detecting a cycle in the graph represented by prerequisites. Both BFS and DFS can be used to solve it using the idea of topological sort. If you find yourself unfamiliar with these concepts, you may refer to their wikipedia pages. Specifically, you may only need to refer to the link in the third hint to solve this problem.

Since pair<int, int> is inconvenient for the implementation of graph algorithms, we first transform it to a graph. If course u is a prerequisite of course v, we will add a directed edge from node u to node v.

BFS

BFS uses the indegrees of each node. We will first try to find a node with 0 indegree. If we fail to do so, there must be a cycle in the graph and we return false. Otherwise we have found one. We set its indegree to be -1 to prevent from visiting it again and reduce the indegrees of all its neighbors by 1. This process will be repeated for n (number of nodes) times. If we have not returned false, we will return true.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<unordered_set<int>> graph = make_graph(numCourses, prerequisites);
vector<int> degrees = compute_indegree(graph);
for (int i = 0; i < numCourses; i++) {
int j = 0;
for (; j < numCourses; j++)
if (!degrees[j]) break;
if (j == numCourses) return false;
degrees[j] = -1;
for (int neigh : graph[j])
degrees[neigh]--;
}
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;
}
vector<int> compute_indegree(vector<unordered_set<int>>& graph) {
vector<int> degrees(graph.size(), 0);
for (auto neighbors : graph)
for (int neigh : neighbors)
degrees[neigh]++;
return degrees;
}
};

DFS

For DFS, it will first visit a node, then one neighbor of it, then one neighbor of this neighbor… and so on. If it meets a node which was visited in the current process of DFS visit, a cycle is detected and we will return false. Otherwise it will start from another unvisited node and repeat this process till all the nodes have been visited. Note that you should make two records: one is to record all the visited nodes and the other is to record the visited nodes in the current DFS visit.

The code is as follows. We use a vector visited to record all the visited nodes and another vector onpath to record the visited nodes of the current DFS visit. Once the current visit is finished, we reset the onpath value of the starting node to false.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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) {
if (visited[node]) return false;
onpath[node] = visited[node] = true;
for (int neigh : graph[node])
if (onpath[neigh] || dfs_cycle(graph, neigh, onpath, visited))
return true;
return onpath[node] = false;
}
};

https://discuss.leetcode.com/topic/13441/bfs-topological-sort-and-dfs-finding-cycle-by-c

BFS(Topological Sort) and DFS(Finding cycle) by C++

  1. BFS(Topological Sort)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
{
vector<unordered_set<int>> matrix(numCourses); // save this directed graph
for(int i = 0; i < prerequisites.size(); ++ i)
matrix[prerequisites[i][1]].insert(prerequisites[i][0]);

vector<int> d(numCourses, 0); // in-degree
for(int i = 0; i < numCourses; ++ i)
for(auto it = matrix[i].begin(); it != matrix[i].end(); ++ it)
++ d[*it];

for(int j = 0, i; j < numCourses; ++ j)
{
for(i = 0; i < numCourses && d[i] != 0; ++ i); // find a node whose in-degree is 0

if(i == numCourses) // if not find
return false;

d[i] = -1;
for(auto it = matrix[i].begin(); it != matrix[i].end(); ++ it)
-- d[*it];
}

return true;
}
  1. DFS(Finding cycle)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
{
vector<unordered_set<int>> matrix(numCourses); // save this directed graph
for(int i = 0; i < prerequisites.size(); ++ i)
matrix[prerequisites[i][1]].insert(prerequisites[i][0]);

unordered_set<int> visited;
vector<bool> flag(numCourses, false);
for(int i = 0; i < numCourses; ++ i)
if(!flag[i])
if(DFS(matrix, visited, i, flag))
return false;
return true;
}
bool DFS(vector<unordered_set<int>> &matrix, unordered_set<int> &visited, int b, vector<bool> &flag)
{
flag[b] = true;
visited.insert(b);
for(auto it = matrix[b].begin(); it != matrix[b].end(); ++ it)
if(visited.find(*it) != visited.end() || DFS(matrix, visited, *it, flag))
return true;
visited.erase(b);
return false;
}

https://discuss.leetcode.com/topic/18734/c-clean-code-for-dfs-solution-with-simple-comments

C++ clean code for DFS solution with simple comments

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool canFinish(int numCourses, vector<pair<int, int>>& prer) {
vector<vector<int>> gragh(numCourses);
vector<int> visited(numCourses, 0); // White at initialization
for (int i = 0; i < prer.size(); i++) {
gragh[prer[i].second].push_back(prer[i].first);
}
bool cycle = false;
for (int i = 0; i < numCourses; i++) {
if (cycle) return false;
if (visited[i] == 0) dfs_top(i, gragh, visited, cycle);
}
return !cycle;
}
void dfs_top(int node, vector<vector<int>> &gragh, vector<int> &visited, bool &cycle) {
if (visited[node] == 1) {cycle = true; return;} // cycle occurs, break the dfs chain and all return
visited[node] = 1; //Gray, searching
for (int i = 0; i < gragh[node].size(); i++) {
dfs_top(gragh[node][i], gragh, visited, cycle);
if (cycle) return; // do some pruning here
}
visited[node] = 2; //Black Once finished.
}

https://discuss.leetcode.com/topic/13412/python-20-lines-dfs-solution-sharing-with-explanation

Python 20 lines DFS solution sharing with explanation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def canFinish(self, numCourses, prerequisites):
graph = [[] for _ in xrange(numCourses)]
visit = [0 for _ in xrange(numCourses)]
for x, y in prerequisites:
graph[x].append(y)
def dfs(i):
if visit[i] == -1:
return False
if visit[i] == 1:
return True
visit[i] = -1
for j in graph[i]:
if not dfs(j):
return False
visit[i] = 1
return True
for i in xrange(numCourses):
if not dfs(i):
return False
return True
  1. if node v has not been visited, then mark it as 0.
  2. if node v is being visited, then mark it as -1. If we find a vertex marked as -1 in DFS, then their is a ring.
  3. if node v has been visited, then mark it as 1. If a vertex was marked as 1, then no ring contains v or its successors.

References: daoluan.net


https://discuss.leetcode.com/topic/25964/ac-python-topological-sort-52-ms-solution-o-v-e-time-and-o-v-e-space

AC Python topological sort 52 ms solution, O(V + E) time and O(V + E) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def canFinish(self, n, pres):
from collections import deque
ind = [[] for _ in xrange(n)] # indegree
oud = [0] * n # outdegree
for p in pres:
oud[p[0]] += 1
ind[p[1]].append(p[0])
dq = deque()
for i in xrange(n):
if oud[i] == 0:
dq.append(i)
k = 0
while dq:
x = dq.popleft()
k += 1
for i in ind[x]:
oud[i] -= 1
if oud[i] == 0:
dq.append(i)
return k == n


# 34 / 34 test cases passed.
# Status: Accepted
# Runtime: 52 ms
# 99.68%

The topological sort is natural for this problem. We always take the courses with no unstudied prereqs and so on until no more courses we can take. The oud[i] is the number of prereqs for course i and indegree keep a list of courses require course i.

谢谢你,可爱的朋友。