There are a total of numCourses courses you have to take, labeled from 0 to numCourses-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: numCourses = 2, prerequisites = [[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: numCourses = 2, prerequisites = [[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.

Constraints:

  • The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  • You may assume that there are no duplicate edges in the input prerequisites.
  • 1 <= numCourses <= 10^5
    Solution in python:

    class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        vertex = [0 for i in range(numCourses)]
        table = {}
        for item in prerequisites:
            if item[1] not in table:
                table[item[1]] = [item[0]]
            else:
                table[item[1]].append(item[0])
            vertex[item[0]] += 1
    
        queue = []
        tag = [1 for i in range(numCourses)] #no need
        for i in range(numCourses):
            if vertex[i] == 0:
                queue.append(i)
                tag[i] = 0
    
        while queue:
            key = queue.pop(0)
            if key in table.keys():
                for item in table[key]:
                    vertex[item] -= 1
                    if vertex[item] == 0:
                        queue.append(item)
                        tag[item] = 0
        if sum(tag) != 0:
            return False
        else: return True

    Complexity analysis:

  • Time complexity: O(a*n+m)
  • Space Complexity: O(a*n+m)
最后修改日期: 2020年9月13日

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。