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)$