207. Course Schedule

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)