207. Course Schedule #

Problem #

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:

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.

Problem Summary #

Now you have a total of n courses to take, labeled from 0 to n-1. Some courses require prerequisites before you can take them. For example, if you want to study course 0, you need to finish course 1 first; we use a pair to represent this: [0,1]. Given the total number of courses and their prerequisites, determine whether it is possible to finish all courses.

Solution Ideas #

• Given n tasks, with dependencies between every two tasks, for example task A must be completed before task B. Determine whether all tasks can be completed.

• This problem is the standard topological sorting problem for an AOV network. The solution to topological sorting is mainly to repeatedly execute the following two steps until there are no vertices with indegree 0.

  • 1. Select a vertex with indegree 0 and output it;
  • 2. Delete this vertex and all outgoing edges from the network.

  After the loop ends, if the number of output vertices is less than the number of vertices in the network, output the information “there is a cycle”, meaning that it is impossible to complete all tasks; otherwise, the output vertex sequence is a topological sequence, meaning that all tasks can be completed.

Code #

package leetcode

// Topological sort of an AOV network
func canFinish(n int, pre [][]int) bool {
	in := make([]int, n)
	frees := make([][]int, n)
	next := make([]int, 0, n)
	for _, v := range pre {
		in[v[0]]++
		frees[v[1]] = append(frees[v[1]], v[0])
	}
	for i := 0; i < n; i++ {
		if in[i] == 0 {
			next = append(next, i)
		}
	}
	for i := 0; i != len(next); i++ {
		c := next[i]
		v := frees[c]
		for _, vv := range v {
			in[vv]--
			if in[vv] == 0 {
				next = append(next, vv)
			}
		}
	}
	return len(next) == n
}