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:


       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.

Difficulty: interview

Starter code:

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        

Solutions:
class Solution(object):
     def canFinish(self, numCourses, prerequisites):
         """
         :type numCourses: int
         :type prerequisites: List[List[int]]
         :rtype: bool
         """
         graph = [[] for _ in range(numCourses)]
         visited = [0 for _ in range(numCourses)]
         # create graph
         for pair in prerequisites:
             x, y = pair
             graph[x].append(y)
         # visit each node
         for i in range(numCourses):
             if not self.dfs(graph, visited, i):
                 return False
         return True
     
     def dfs(self, graph, visited, i):
         # if ith node is marked as being visited, then a cycle is found
         if visited[i] == -1:
             return False
         # if it is done visted, then do not visit again
         if visited[i] == 1:
             return True
         # mark as being visited
         visited[i] = -1
         # visit all the neighbours
         for j in graph[i]:
             if not self.dfs(graph, visited, j):
                 return False
         # after visit all the neighbours, mark it as done visited
         visited[i] = 1
         return True

class Solution:
     def canFinish(self, numCourses, prerequisites):
         """
         :type numCourses: int
         :type prerequisites: List[List[int]]
         :rtype: bool
         """
         V = numCourses
         
         # Store outgoing edges
         edges = []
         
         for _ in range(V):
             edges.append(set())
         
         for p in prerequisites:
             # Edge goes from v1 to v2
             v2, v1 = p
             edges[v1].add(v2)
         
         checked = set()
         
         def detect_cycle(x, visited):
             visited.add(x)
             checked.add(x)
             
             for v in edges[x]:
                 if v in visited:
                     return True
                 if detect_cycle(v, visited):
                     return True
             visited.remove(x)
             return False
         
         for v in range(V):
             if v in checked:
                 continue
             if detect_cycle(v, set()):
                 return False
         
         return True
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         


class Solution:
     def canFinish(self, numCourses, prerequisites):
         """
         :type numCourses: int
         :type prerequisites: List[List[int]]
         :rtype: bool
         """
         
         # sol1: topo sort
         N = numCourses
         indegree = [0] * N
         O = [set() for _ in range(N)]
         for b, a in prerequisites:
             O[a].add(b)
             indegree[b] += 1
         
         stack = [c for c in range(N) if indegree[c] == 0]
         done = 0
         while stack:
             i = stack.pop()
             done += 1
             for j in O[i]:
                 indegree[j] -= 1
                 if indegree[j] == 0:
                     stack.append(j)
         return done == N
         
         # sol2: UF


class Solution:
     def canFinish(self, numCourses, prerequisites):
         """
         :type numCourses: int
         :type prerequisites: List[List[int]]
         :rtype: bool
         """
         pre_count = [0] * numCourses
         next_courses = [[] for _ in range(numCourses)]
         
         for cur, pre in prerequisites:
             next_courses[pre].append(cur)
             pre_count[cur] += 1
         
         q = []
         
         # always chose courses without prereq
         for i, count in enumerate(pre_count):
             if count == 0:
                 q.append(i)
         
         finish_num = 0
         # take those courses which can be taken after finishing prereq
         while q:
             course = q.pop(0)
             finish_num += 1
             for next_course in next_courses[course]:
                 pre_count[next_course] -= 1
                 if pre_count[next_course]  == 0:
                     q.append(next_course)
         
         return finish_num == numCourses
             
         


class Solution:
     def canFinish(self, numCourses, prerequisites):
         """
         :type numCourses: int
         :type prerequisites: List[List[int]]
         :rtype: bool
         """
         graph = [[] for _ in range(numCourses)]
         visit = [0 for _ in range(numCourses)]
         for x, y in prerequisites:
             graph[x].append(y)
             
         ## states: 0 = unkonwn, 1 == visiting, 2 = visited
         def dfs(c,v):
             if v[c] == 2: return False
             if v[c] == 1: return True
             v[c]=1 #lable as visiting, if it does not visited eventually, it will cause an exception
             for i in graph[c]:
                 if dfs(i,v): return True
                 
             v[c]=2 # change to visited after done visiting
             return False
         
         
         for j in range(numCourses):
             if dfs(j,visit): return False
         return True
             


class Solution:
     def canFinish(self, numCourses, prerequisites):
         """
         :type numCourses: int
         :type prerequisites: List[List[int]]
         :rtype: bool
         """       
         in_degrees = collections.defaultdict(int)        
         edges = collections.defaultdict(list)
 
         for i in range(0, numCourses):
             in_degrees[i] = 0            
         
         for prerequisty in prerequisites:
             start = prerequisty[1]
             end = prerequisty[0]
             edges[start].append(end)
             in_degrees[end] += 1
 
         queue = collections.deque()
         
         for i in range(0, numCourses):
             if in_degrees[i] == 0:
                 queue.append(i)
             
         count = 0
         while len(queue) > 0:
             node = queue.popleft()
             count += 1
             
             for neighbor in edges[node]:
                 in_degrees[neighbor] -= 1
                 if in_degrees[neighbor] == 0:
                     queue.append(neighbor)
                     
         return count == numCourses        

class Solution:
     def canFinish(self, numCourses, prerequisites):
         """
         :type numCourses: int
         :type prerequisites: List[List[int]]
         :rtype: bool
         """
         course_map = {i: [] for i in range(numCourses)}
         degree = [0 for i in range(numCourses)]
         q = []
         counter = 0
         for c,p in prerequisites:
             course_map[c].append(p)
             degree[p] += 1
         
         for i in range(numCourses):
             if degree[i] == 0:
                 q.append(i)
                 counter += 1
         while q:
             cur = q.pop(0)
             for p in course_map[cur]:
                 degree[p] -= 1
                 if degree[p] == 0:
                     q.append(p)
                     counter += 1
         
         return counter == numCourses


class Solution:
     def canFinish(self, n, prerequisites):
         """
         :type numCourses: int
         :type prerequisites: List[List[int]]
         :rtype: bool
         """
         def ok(node):
             if seens[node] == -1:
                 return False
             if not seens[node]:
                 seens[node] = -1
                 for pre in pres[node]:
                     if not ok(pre):
                         return False
                 seens[node] = 1
             return True
         
         pres = [[] for _ in range(n)]
         for cur, pre in prerequisites:
             pres[cur].append(pre)
         
         seens = [0] * n
         for node in range(n):
             if not ok(node):
                 return False
         return True

class Solution:
     def canFinish(self, numCourses, prerequisites):
         """
         :type numCourses: int
         :type prerequisites: List[List[int]]
         :rtype: bool
         """
         from collections import deque
         class Vertex(object):
             def __init__(self):
                 self.inDegree = 0
                 self.visited = False
                 self.adjList = []
                 self.invAdjList = []
             def info(self):
                 print(self.adjList)
                 print(self.invAdjList, self.inDegree)
                 print(self.visited)
         #initialization
         vertices = []
         for _ in range(numCourses):
             vertices.append(Vertex())
 
         for i in prerequisites:
             pre = i[0]
             post = i[1]
             vertices[pre].adjList.append(post)
             vertices[post].inDegree += 1
             vertices[post].invAdjList.append(pre)
 
         #BFS
         q = deque()
         coursesLearned = []
         for i in range(numCourses):
             if vertices[i].inDegree == 0:
                 q.append(i)
 
         while q:
             course = q.popleft()
             coursesLearned.append(course)
             vertices[course].visited = True
             for c2 in vertices[course].adjList:
                 vertices[c2].inDegree -= 1
                 if vertices[c2].inDegree == 0:
                     q.append(c2)
         return len(coursesLearned) == numCourses

class Solution:
     def canFinish(self, numCourses, prerequisites):
         """
         :type numCourses: int
         :type prerequisites: List[List[int]]
         :rtype: bool
         """
         
         N = numCourses
         
 #         # sol1: topo sort
 #         indegree = [0] * N
         O = [set() for _ in range(N)]
         for b, a in prerequisites:
             O[a].add(b)
 #             indegree[b] += 1
             
 #         q = [c for c in range(N) if indegree[c] == 0]
 #         done = 0
 #         while q:
 #             c = q.pop()
 #             done += 1
 #             for post in O[c]:
 #                 indegree[post] -= 1
 #                 if indegree[post] == 0:
 #                     q.append(post)
 #         return done == N # CAUTION
         
         # sol2: dfs
         color = [0] * N
         def dfs(i):
             if color[i] == -1:
                 return False
             elif color[i] == 1:
                 return True
             color[i] = -1
             if any(not dfs(j) for j in O[i]):
                 return False
             color[i] = 1
             return True
         
         return all(map(dfs, range(N)))

class Solution:
     def canFinish(self, numCourses, prerequisites):
         """
         :type numCourses: int
         :type prerequisites: List[List[int]]
         :rtype: bool
         """
         N = numCourses
         
 #         # sol1: topo sort
 #         pre = [0] * N
 #         O = [set() for _ in range(N)]
 #         for b, a in prerequisites:
 #             O[a].add(b)
 #             pre[b] += 1
             
 #         stack = [c for c in range(N) if not pre[c]]
 #         done = 0
 #         while stack:
 #             c = stack.pop()
 #             done += 1
 #             for post in O[c]:
 #                 pre[post] -= 1
 #                 if pre[post] == 0:
 #                     stack.append(post)
 #         return done == N
         
         # sol2: dfs
         O = [set() for _ in range(N)]
         for b, a in prerequisites:
             O[a].add(b) # it's O, not I
         visit = [0] * N
             
         def dfs(i):
             if visit[i] == -1:
                 return False
             elif visit[i] == 1:
                 return True
             
             visit[i] = -1
             if any(not dfs(j) for j in O[i]): # "not" dfs(j)
                 return False
             visit[i] = 1
             return True
         
         return all(map(dfs, range(N)))

class Solution:
     def canFinish(self, numCourses, prerequisites):
         """
         :type numCourses: int
         :type prerequisites: List[List[int]]
         :rtype: bool
         """
         edges = {i: [] for i in range(numCourses)}
         degree = [0 for i in range(numCourses)]
         
         for k, v in prerequisites:
             edges[v].append(k)
             degree[k] += 1
         
         q = []
         for i in range(numCourses):
             if degree[i] == 0:
                 q.append(i)
         
         count = 0
         while q:
             node = q.pop()
             count += 1
             for nn in edges[node]:
                 degree[nn] -= 1
                 if degree[nn] == 0:
                     q.append(nn)
         return count == numCourses