# Python beat 96%. With idea description and comments

• See comment for ideas.

class Solution(object):

"""
This problem is about build tree + DFS.
When DFS, check for circle (any children are already on the PATH)

build tree: according to prerequisites, build a tree (actually graph) where a -> b mean a is prerequisite for b. (here I use parentChildren to record tree structure. You can also use you own class to do this)

Then start from each node (i.e. course) and do DFS. When the child is on the path, circle detected -> not good, return False
"""
def DFS(self, root, onPath, parentChildren, explored):
if not parentChildren.has_key(root):
# it means root does not have any children (i.e., it is not prerequisite of any classes)
del onPath[root]
return True

for i in range(len(parentChildren[root])):
child = parentChildren[root][i]

# circle detected
if onPath.has_key(child): return False

# if we have explored this course, do nothing
if explored.has_key(child):
continue

onPath[child] = 1
explored[child] = 1

if self.DFS(child, onPath, parentChildren, explored) == False:
return False
del onPath[root]
return True

def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: bool
"""
coursesPool = []
parentChildren = {}

# parentChildren will record the graph structure.
for pair in prerequisites:
if parentChildren.has_key(pair[0]):
parentChildren[pair[0]].append(pair[1])
else:
parentChildren[pair[0]] = [pair[1]]

parentChildren[-1] = [key for key in range(numCourses)]
#print parentChildren
onPath = {-1:1}
explored = {}
return self.DFS(-1, onPath, parentChildren, explored)

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