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: self.adj[i].add(j) #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 for i in xrange(len(self.adj)): 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 self.visited.add(v) possible = True #For every vertex adjecent to v for u in self.adj[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) self.completed.add(v) return possible