class Solution:
# @param {integer} numCourses
# @param {integer[][]} prerequisites
# @return {boolean}
def canFinish(self, numCourses, prerequisites):
graph = {}
for c, p in prerequisites:
if c not in graph:
graph[c] = []
if p not in graph[c]:
graph[c].append(p)
course_taken = []
required_done = lambda c: c in graph and all([req in course_taken for req in graph[c]])
while len(graph):
crawled = []
c = graph.items()[0][0]
stack = [c]
while stack:
c = stack.pop()
if c in course_taken:
continue
if c in crawled:
return False
crawled.append(c)
if c in graph:
r = graph[c]
stack.extend(r)
while crawled:
r = crawled.pop()
if r in graph and not required_done(r):
continue
if r not in course_taken:
course_taken.append(r)
if required_done(r):
del graph[r]
return True
Python DFS solution for Course Schedule


The problem declaration is ambiguous. If "one node is reachable only if ALL of its parents are reached",then detecting cycle solution is right. Else if "one node is reachable if ONE of its parent is reached", then solution can be much simpler, because you only need to find "independent nodes", and to see if they are connected to other nodes.