LeetCode 207. 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 1:
Input: 2,[[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should
also have finished course 1. So it is impossible.
描述
现在你总共有 n 门课需要选，记为 0 到 n-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。这是不可能的。
思路
- 本题考察图，本题使用广度优先搜索.
- 我们构建一个字典，值为当前课程，值为数组，list中包含当前课程结束接着可以上的课程.
- 我们维护一个数组，数组中的值为数组索引所对应课程需要多少个前驱课程，如list[4]=7,表示要上4号课程，之前要上节课程.
- 我们使用一个队列进行深度右边遍历，先遍历入度为0的课程，每次遍历一个课程就将该课程的下一个课程入度减一，同时检查下一个课程是否被减到了0，若是则将其添加到队列尾，进行下一次遍历.最后我们检查所有课程的入度，如果所有的课程入度都为0，说明所有的课程都已经上完，若不是则说明还有课程无法上完，我们返回False.
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2019-01-21 12:05:36
# @Last Modified by: 何睿
# @Last Modified time: 2019-01-21 20:26:27
from collections import deque
class Solution:
def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: bool
"""
if not numCourses: return 0
nextcourse, indegree = {}, [0] * numCourses
# 构建字典，键为课程，值为上完编号为键的课可以上的下一节课
for item in prerequisites:
if item[1] not in nextcourse:
nextcourse[item[1]] = [item[0]]
else:
nextcourse[item[1]].append(item[0])
# 统计每一个课程的入度
indegree[item[0]] += 1
# 统计入度为0的课程
queue = deque()
for i in range(numCourses):
if not indegree[i]: queue.append(i)
# 只要有入度为0的课程就继续循环
while queue:
c = queue.popleft()
# 下一次将要上的课程
for _next in nextcourse.get(c, []):
# 当前课程已经上了，下一节课入度减一
indegree[_next] -= 1
# 将新产生的入度为0的课程添加到队列中
if not indegree[_next]: queue.append(_next)
for item in indegree:
if item: return False
return True
