【leetcode】207. Course Schedule

深藏阁楼爱情的钟 2022-01-07 11:29 189阅读 0赞

**题目如下：**

> 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.
> 
> Note:
> 
> 1.  The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about [how a graph is represented][].
> 2.  You may assume that there are no duplicate edges in the input prerequisites.

**解题思路：**如果某一种输入课程无法被安排，那么一定存在至少这样一门课：通过BFS/DFS的方法从这门课开始，依次遍历需要安排在这门课后面的其他课，最终还会回到这门课，即组成了一个环。我们只有遍历所有的课，看看有没有哪门课会形成环路即可。

**代码如下：**

class Solution(object):
        def canFinish(self, numCourses, prerequisites):
            """
            :type numCourses: int
            :type prerequisites: List[List[int]]
            :rtype: bool
            """
            dic = {}
            for cou,pre in prerequisites:
                if pre not in dic:
                    dic[pre] = [cou]
                else:
                    dic[pre].append(cou)
    
            for i in range(numCourses):
                visit = [0] * numCourses
                queue = [i]
                start = None
                while len(queue) > 0:
                    inx = queue.pop(0)
                    if start == None:
                        start = inx
                    elif inx == start:
                        return False
                    if visit[inx] == 1:
                        continue
                    visit[inx] = 1
                    if inx in dic and len(dic[inx]) > 0:
                        queue += dic[inx]
            return True

转载于:https://www.cnblogs.com/seyjs/p/10456295.html

[how a graph is represented]: https://www.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs