前言
持续更新了
正文
问题来源
本问题来自leetcode上的207题。
问题描述
你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
示例 1:
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
示例 2:
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
分析：
func canFinish(numCourses int, prerequisites [][]int) bool {
var (
can bool
visit []int
edge [][]int
dfs func(u int)
)
dfs = func(u int) {
visit[u] = 1
for _, v := range edge[u] {
if visit[v] == 0 {
dfs(v)
if !can {
return
}
} else if visit[v] == 1 {
can = false
return
}
}
visit[u] = 2
}
// init
can = true
visit = make([]int, numCourses)
edge = make([][]int, numCourses)
for _, v := range prerequisites {
edge[v[1]] = append(edge[v[1]], v[0])
}
for i := 0; i < numCourses; i++ {
dfs(i)
if !can {
return false
}
}
return true
}
总结：
勤思考。
结语
不管怎么样好好加油。
