• ``````# BFS: from the end to the front
def canFinish1(self, numCourses, prerequisites):
forward = {i: set() for i in xrange(numCourses)}
backward = collections.defaultdict(set)
for i, j in prerequisites:
queue = collections.deque([node for node in forward if len(forward[node]) == 0])
while queue:
node = queue.popleft()
for neigh in backward[node]:
forward[neigh].remove(node)
if len(forward[neigh]) == 0:
queue.append(neigh)
forward.pop(node)
return not forward  # if there is cycle, forward won't be None

# BFS: from the front to the end
def canFinish2(self, numCourses, prerequisites):
forward = {i: set() for i in xrange(numCourses)}
backward = collections.defaultdict(set)
for i, j in prerequisites:
queue = collections.deque([node for node in xrange(numCourses) if not backward[node]])
count = 0
while queue:
node = queue.popleft()
count += 1
for neigh in forward[node]:
backward[neigh].remove(node)
if not backward[neigh]:
queue.append(neigh)
return count == numCourses

# DFS: from the end to the front
def canFinish3(self, numCourses, prerequisites):
forward = {i: set() for i in xrange(numCourses)}
backward = collections.defaultdict(set)
for i, j in prerequisites:
stack = [node for node in forward if len(forward[node]) == 0]
while stack:
node = stack.pop()
for neigh in backward[node]:
forward[neigh].remove(node)
if len(forward[neigh]) == 0:
stack.append(neigh)
forward.pop(node)
return not forward

# DFS: from the front to the end
def canFinish(self, numCourses, prerequisites):
forward = {i: set() for i in xrange(numCourses)}
backward = collections.defaultdict(set)
for i, j in prerequisites:
stack = [node for node in xrange(numCourses) if not backward[node]]
while stack:
node = stack.pop()
for neigh in forward[node]:
backward[neigh].remove(node)
if not backward[neigh]:
stack.append(neigh)
backward.pop(node)
return not backward``````

• Hi, can you help me to spot what is wrong with my code, which cannot pass the test-case of 2000 courses.
Thanks!

``````import collections
class Solution(object):
def canFinish(self, numCourses, prerequisites):
if not numCourses:
return False
elif not prerequisites:
return True
else:
require = collections.defaultdict(list) # to save prerequisites
for pair in prerequisites:
require[pair[0]].append(pair[1])
path = []
for i in xrange(numCourses):
if not self.DFS(i, require, path):
return False
return True

def DFS(self, i, require, path):
# do DFS for i
if i in path: return False # cycle
for j in require[i]:
if not self.DFS(j, require, path + [i]):
return False
return True``````

• You answer seems correct but "Time Limit Exceeded". It should be better if can change your code to iterative dfs by using explicit stack instead of using recursion.

• sure. Thank you so much!

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