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
源代码文件在这里.
