0207. Course Schedule

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

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.

## 解题思路 #

• 给出 n 个任务，每两个任务之间有相互依赖关系，比如 A 任务一定要在 B 任务之前完成才行。问是否可以完成所有任务。

• 这一题就是标准的 AOV 网的拓扑排序问题。拓扑排序问题的解决办法是主要是循环执行以下两步，直到不存在入度为0的顶点为止。

1. 选择一个入度为0的顶点并输出之；
1. 从网中删除此顶点及所有出边。

循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，即无法完成所有任务；否则输出的顶点序列就是一种拓扑序列，即可以完成所有任务。

## 代码 #

``````
package leetcode

// AOV 网的拓扑排序
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
}

``````

Apr 8, 2023
Edit this page