Python solution using DFS with comments


  • 0
    T

    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

Log in to reply
 

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