Day.20 Course Schedule

Leetcode #207. Course Schedule

题目给你一系列的课程，每一个门课都有它的先修课，你要判断它能不能完成全部的课程。
来举个例子:
Input: numCourses = 2, prerequisites = [[0,1],[0,4],[1,2],[2,0]]
prerequisites里面放的两维array是Edge List储存图的方式，现在把它画成图。

完成0的课，需要先完成1、4，4的课没有其他先修课，4是可以被完成的。1的先修是2，2的先修是0，结果又回到0，会造成无限的loop。
这时候我们就回传false，表示不可能完成全部的课程。

换句话来说，我们检查图有没有cycle就可以了!

这题会用DFS来解(你用BFS也可以)
用一个map来记下走过的课程，当0->1->2的时候，2又回到0就可以发现有cycle。
每一个课程都做一次DFS，基本上就解出来了，不过这做法的时间复杂度很高，会到O(n^2)，会有大量的重复走访，在这一题leetcode会跑到timeout (惨痛经验 XD
需要在这基础上做优化，来换个例子解释～

像这种情境，从课程0 DFS出去，0->1->2都没有发现cycle。
这时候0、1、2，这几个点都已经被检查完成了，我们记录下来，之後换到4做DFS，就不用再跑去1->2做重复的检查，时间复杂度会降到O(m+n)，每一个课程+边线都走一次，不会重复。

所以现在有两个map要记

1. 记录当下DFS的路线，用於检查有没有cycle
2. 记录DFS完的课程，用於避免重复的检查

把它写成程序～

func canFinish(numCourses int, prerequisites [][]int) bool {
	// 先把Edge list格式转成Adjacency list
    // ex: 0:[1,4] 1:[2]
	adjList := map[int][]int{}
	for _, pre := range prerequisites {
		adjList[pre[0]] = append(adjList[pre[0]], pre[1])
	}

	traced := map[int]bool{}
	checked := map[int]bool{}
	// 每个点都要做一次DFS哦
	for i := 0; i < numCourses; i++ {
		if hasCycle(i, adjList, traced, checked) {
			return false
		}
	}

	return true
}

func hasCycle(course int, adjList map[int][]int, traced, checked map[int]bool) bool {
	// 如果之前走过，证明是有cycle
	if traced[course] {
		return true
	}

	// 检查之前有没有检查过，如果有就不重复
	if checked[course] {
		return false
	}

	traced[course] = true
	for _, pre := range adjList[course] {
		if hasCycle(pre, adjList, traced, checked) {
			return true
		}
	}
	// *这个map是用来记每个点DFS的记录 走完要改回false
	traced[course] = false

	// DFS完 代表检查完成 没有cycle
	checked[course] = true

	return false
}

感谢大家～