# Python solution using DFS with comments

• I couldn't find a clean python solution, so posting mine. Any suggestions for improvements?

``````class Solution(object):
"""
This is an instance of finding a cycle in a graph. We can do simple DFS to detect it.
"""
def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: bool
"""
if numCourses == 1:
return True

#Convert the edges into an adjecency list representation
self.adj = [set() for i in xrange(numCourses)]

for i,j in prerequisites:

#visited set will track vertices seen while exploring the current vertex
self.visited = set()

#completed set will track vertices that have been completely explored
self.completed = set()

#For every vertex that has not been explored, visit it
if i not in self.visited and i not in self.completed:
possible = self.visit(i)
if not possible:
return False

#when all the vertices have been explored without cycles, we can return True
return True

def visit(self, v):
#mark the current vertex as visited
possible = True

#For every vertex adjecent to v

#explore the vertex only if not already explored
if u not in self.completed and u not in self.visited:
possible = possible and self.visit(u)

#if this vertex was seen during the exploration of current vertex,
#then there is a cycle in the graph and we can return False
if u in self.visited:
possible = False
break

#finally, we can mark the current vertex as completely explored
self.visited.remove(v)