615. Course Schedule

Description

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

Example 1:

Input: n = 2, prerequisites = [[1,0]]

Output: true

Example 2:

Input: n = 2, prerequisites = [[1,0],[0,1]]

Output: false

思路：

将问题转化成求是否存在拓扑序列的算法问题， 只要存在拓扑序列，那么课程就可以修完。

明确这一点之后，需要知道一个图的各个点的入度， 以及边的集合，这时候就需要将题目信息转化为入度与边的集合。（这里答案实现的很巧妙，利用了给定数组两者之间的关系，用一个dict 一个list实现了要求）

准备好之后，就可以用宽度优先搜索去遍历所有点，求是否存在拓扑序列。

代码