```
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:
In[pair[0]].add(pair[1])
Out[pair[1]].add(pair[0]) #
# Find and start with all nodes with no incoming edges
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
```