Reference: Problem I, Problem II
Difficulty: Medium

My Post: [Java] Course Schedule I & II (DFS + BFS) 超级大饭团

Problem I

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?

Note:

  • The input is represented by a list of edges, not adjacency matrices or list.
  • You may assume that there are no duplicate edges in the input prerequisites.

Example:

1
2
3
4
5
6
7
8
9
10
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.

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.

DFS (Cycle Detection)

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.

My mistake: Using only true/false marked array does not solve the problem. We need more information because we are not dealing with a problem like finding a cycle in a path.

Reference: Python 20 lines DFS solution sharing with explanation

marked array has three states:

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

Note: First, we convert the input to a graph represented by an adjacency list (gain efficiency).

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
32
public boolean canFinish(int numCourses, int[][] preReq) {
if (numCourses == 0 || preReq == null || preReq.length == 0) {
return true; // or false
}
// convert to adjacency list O(E)
List<List<Integer>> graph = new ArrayList<>();
for (int v = 0; v < numCourses; ++v) graph.add(new ArrayList<>()); // init
for (int[] edge : preReq) {
graph.get(edge[1]).add(edge[0]);
}
// dfs
int[] marked = new int[numCourses];
for (int v = 0; v < numCourses; ++v) { // O(V)
if (dfs(v, graph, marked)) return false; // O(E) in total
}
return true; // no cycle -> can finish
}

// Returns true if a cycle is detected.
private boolean dfs(int v, List<List<Integer>> graph, int[] marked) {
// not visited: 0 | being visited: -1 | visited: +1
marked[v] = -1; // visit
// for each neighbor
for (int w : graph.get(v)) {
if (marked[w] == -1) return true; // cycle exists
if (marked[w] == 0) { // not visited
if (dfs(w, graph, marked)) return true;
}
}
marked[v] = +1; // visited
return false; // no cycle is detected
}

Time: $O(V + E)$
Space: $O(V)$

BFS (Topological Sort)

The problem can be reduced to the one that finds if there is a topological sort in the graph (also equivalent to the one that finds if the graph is acyclic).

There are two ways of finding a topological sort: Reversed DFS and BFS. We pick BFS at this time.

The basic idea is that we add all nodes with 0 degrees into a queue, and do BFS from these nodes. They are the starting nodes in a graphs.

Each time we poll a node from the queue, we decrease all its neighbors’ in-degree by one. This is like deleting the node from the graph and removing all its outgoing edges. If a topological sort exists, we can remove the whole graph!

The whole process takes $O(V)$ steps in total if there is a topological sort.

Two Cases

So we need a count variable to check how many steps we have along this process. If it finally reduces to 0, then there is a 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
26
27
28
29
30
31
32
33
34
35
36
public boolean canFinish(int numCourses, int[][] preReq) {
if (numCourses == 0 || preReq == null || preReq.length == 0) {
return true; // or false
}
// convert to adjacency list
List<List<Integer>> graph = new ArrayList<>();
int[] indegree = new int[numCourses];
for (int v = 0; v < numCourses; ++v) graph.add(new ArrayList<>()); // init
for (int[] edge : preReq) {
graph.get(edge[1]).add(edge[0]); // edge[1] is the prerequisite of edge[0]
indegree[edge[0]] += 1; // count indegree for each node
}
// bfs
Queue<Integer> queue = new LinkedList<>();
int count = numCourses;
// push all 0-degree nodes
for (int v = 0; v < numCourses; ++v) {
if (indegree[v] == 0) { // starting nodes
queue.offer(v);
}
}

while (queue.size() > 0) {
int v = queue.poll();
// for each neighbor w
for (int w : graph.get(v)) {
--indegree[w];
if (indegree[w] == 0) {
queue.offer(w);
}
}
--count;
}

return count == 0;
}

Time: $O(V + E)$
Space: $O(V)$

Problem II

DFS (Reversed Post-Order Traversal)

Reference: CS 61B | Part 11 | Topological Sort, DAG-LPT, DAG-SPT, DP, LIS / LLIS

Based on the version of cycle detection, we can update it to construct a topological ordering.

  1. Perform a DFS traversal from every vertex (any order) in the graph, not clearing markings between traversals (means not traversing marked vertices).
  2. Record DFS post-order along the way (add to list when backtracking).
  3. Topological ordering is the reverse of the post-order.
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public int[] findOrder(int numCourses, int[][] preReq) {
if (numCourses == 0) return null;
if (preReq == null || preReq.length == 0) { // no constraint
int[] result = new int[numCourses];
for (int i = 0; i < numCourses; ++i) result[i] = i;
return result;
}
// convert to adjacency list
List<List<Integer>> graph = new ArrayList<>();
int[] indegree = new int[numCourses];
for (int v = 0; v < numCourses; ++v) graph.add(new ArrayList<>()); // init
for (int[] edge : preReq) {
graph.get(edge[1]).add(edge[0]);
}
// dfs
List<Integer> result = new ArrayList<>();
int[] marked = new int[numCourses];
for (int v = 0; v < numCourses; ++v) {
if (marked[v] == 0) {
if (dfs(v, marked, graph, result)) { // returns true if a cycle is detected
return new int[0]; // no topological sort
}
}
}
// convert to array
int[] output = new int[result.size()];
for (int i = 0; i < result.size(); ++i) {
output[i] = result.get(result.size() - i - 1);
}
return output;
}

// Returns true if a cycle is detected.
private boolean dfs(int v, int[] marked, List<List<Integer>> graph, List<Integer> result) {
marked[v] = -1; // being visited
// for each neighbor
for (int w : graph.get(v)) {
if (marked[w] == -1) { // cycle detected!
return true;
}
if (marked[w] == 0) {
if (dfs(w, marked, graph, result)) return true;
}
}
marked[v] = +1; // visited
result.add(v); // post-order dfs
return false;
}

Time: $O(V + E)$
Space: $O(V)$

BFS (Simpler)

Return a node list in topological ordering. Use BFS. Add to the list when a node is polled from the queue.

Note:

  • Base case! When there is no prerequisite, return a list of all nodes.
  • When there is no topological sort, return an empty array.
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
32
33
34
35
36
37
38
39
40
41
42
43
44
public int[] findOrder(int numCourses, int[][] preReq) {
if (numCourses == 0) return null;
if (preReq == null || preReq.length == 0) { // no constraint
int[] result = new int[numCourses];
for (int i = 0; i < numCourses; ++i) result[i] = i;
return result;
}
// convert to adjacency list
List<List<Integer>> graph = new ArrayList<>();
int[] indegree = new int[numCourses];
for (int v = 0; v < numCourses; ++v) graph.add(new ArrayList<>()); // init
for (int[] edge : preReq) {
graph.get(edge[1]).add(edge[0]);
indegree[edge[0]] += 1; // count indegree for each node
}
// bfs
int[] result = new int[numCourses];
int count = 0;
Queue<Integer> queue = new LinkedList<>();
for (int v = 0; v < numCourses; ++v) {
if (indegree[v] == 0) {
queue.offer(v);
}
}

while (queue.size() > 0) {
int v = queue.poll();
result[count++] = v;
// for each of its neighbors
for (int w : graph.get(v)) {
--indegree[w];
if (indegree[w] == 0) {
queue.offer(w);
}
}
}

// check if there is topologial sort
if (count == numCourses) {
return result;
} else {
return new int[0];
}
}

Time: $O(V + E)$
Space: $O(V)$


Comment