207. 课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则必须先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

拓扑排序 BFS

 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
func canFinish(numCourses int, prerequisites [][]int) bool {
	count := 0
	// 入度表
	inDegrees := make([]int, numCourses)
	for _, p := range prerequisites {
		inDegrees[p[0]]++
	}
	// 邻接表
	edgeMap := map[int][]int{}
	for _, p := range prerequisites {
		if _, ok := edgeMap[p[1]]; !ok {
			edgeMap[p[1]] = []int{p[0]}
		} else {
			edgeMap[p[1]] = append(edgeMap[p[1]], p[0])
		}
	}
	// 队列
	queue := make([]int, 0)
	// 入度为0的节点入队
	for i, inDegree := range inDegrees {
		if inDegree == 0 {
			queue = append(queue, i)
		}
	}

	for len(queue) != 0 {
		// 出队 代表学过
		i := queue[0]
			
		count++
		if edgeNodes, ok := edgeMap[i]; ok && len(edgeNodes) > 0 {
			// i有后续节点
			for _, edgeNode := range edgeNodes {
				// 后续节点入度-1
				inDegrees[edgeNode]--
				if inDegrees[edgeNode] == 0 {
					// 若后续节点入度为0，入队
					queue = append(queue, edgeNode)
				}
			}
		}
	}
	return count == numCourses
}

DFS

类似，一条路走到黑

 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
func canFinish(numCourses int, prerequisites [][]int) bool {
	count := 0
	// 入度表
	inDegrees := make([]int, numCourses)
	for _, p := range prerequisites {
		inDegrees[p[0]]++
	}
	// 邻接表
	edgeMap := map[int][]int{}
	for _, p := range prerequisites {
		if _, ok := edgeMap[p[1]]; !ok {
			edgeMap[p[1]] = []int{p[0]}
		} else {
			edgeMap[p[1]] = append(edgeMap[p[1]], p[0])
		}
	}

	var dfs func(node int)
	dfs = func(node int) {
		count++
		if edgeNodes, ok := edgeMap[node]; ok && len(edgeNodes) > 0 {
			// 遍历后续节点
			for _, edgeNode := range edgeNodes {
				inDegrees[edgeNode]--
				if inDegrees[edgeNode] == 0 {
					// 入度为0 可以学了
					dfs(edgeNode)
				}
			}
		}
	}
	// 记录一下入度为0的节点 因为之后dfs的时候会变
	zeroInDegrees := make([]int, 0)
	for i, inDegree := range inDegrees {
		if inDegree == 0 {
			zeroInDegrees = append(zeroInDegrees, i)
		}
	}
	for _, zeroInDegree := range zeroInDegrees {
		dfs(zeroInDegree)
	}
	return count == numCourses
}

判断环的 DFS

不想写了，理解就好