207.M 课程表

Problem: 207. 课程表

思路

广度优先搜索。

• 用graph来存储图，比如依赖A的节点有[B,C]。

• 用indegree存储节点的入度

最开始先把入度为0的节点加入队列，开始广度优先搜索。遍历到每个节点后，把依赖该节点的节点的入度降低，如果某个节点的入度为0，则加入队列进行广度优先搜索。

最终看访问到的节点数量和课程数量是否一致。

Code

func canFinish(numCourses int, prerequisites [][]int) bool {
	graph := make(map[int][]int)  // 存储依赖A的节点有[B,C]
	indegree := make(map[int]int) // 存储每个节点的入度
	for _, pair := range prerequisites {
		graph[pair[1]] = append(graph[pair[1]], pair[0])
		indegree[pair[0]]++
	}

	var q []int
	for i := 0; i < numCourses; i++ {
		if indegree[i] == 0 {
			q = append(q, i)
		}
	}

	visited := 0
	for len(q) > 0 {
		cur := q[0]
		q = q[1:]

		visited++
		for _, v := range graph[cur] {
			// 降低依赖该节点的节点的入度
			indegree[v]--
			if indegree[v] == 0 {
				// 入度为0，则表示可以学习了
				q = append(q, v)
			}
		}
	}

	return visited == numCourses
}