# Simple BFS linear time solution, 14 line, intuitive with comments

• ``````class Solution:
# @param {integer} numCourses
# @param {integer[][]} prerequisites
# @return {boolean}
def canFinish(self, numCourses, prerequisites):
# BFS with linear O(V+E) time and space
# Incoming Edge Set: In[n]: set of courses that need to be finished before couse n
# Outgoing Edge Set: Out[n]: set of courses that need to be finished after course n
In =  [set() for n in range(numCourses)]
Out = [set() for n in range(numCourses)]
for pair in prerequisites:

import collections
Q = collections.deque([n for n in range(numCourses) if not In[n]])
while Q:
cur = Q.pop()
while Out[cur]:
# remove all outgoing edges: cur->nex
nex = Out[cur].pop()
In[nex].remove(cur)
# if nex has no other incoming edges, it is safe to finish nex
if not In[nex]:
Q.append(nex)
# All nodes visited in order = nothing left in the adjacency list
return False if any(Out) else True``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.