Python solution using DFS with comments

  • 0

    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
            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
            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
            #finally, we can mark the current vertex as completely explored
            return possible

Log in to reply

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