# BFS(Topological Sort) Python solution with comments

• ``````class Solution:
# @param {integer} numCourses
# @param {integer[][]} prerequisites
# @return {boolean}
def canFinish(self, numCourses, prerequisites):
# prerequisites graph, course as v, prers as e
# use dict for prers as convenience
prer_graph = {course:{} for course in xrange(numCourses)}
counts = 0
finished_course_list = []

# construct graph
for course, prer in prerequisites:
prer_graph[course][prer] = True

# get no incoming edge v
for course in xrange(numCourses):
if not prer_graph[course]:
finished_course_list.append(course)

# remove edge from graph, and find other no incoming edge v
while finished_course_list:
counts += 1
finished_course = finished_course_list.pop()
for course, prers in prer_graph.iteritems():
if finished_course in prers:
del prers[finished_course]
if len(prers) == 0:
finished_course_list.append(course)

return counts == numCourses
``````

Implementation of http://en.wikipedia.org/wiki/Topological_sorting

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