My iterative dfs (cause why not) Python solution with adjacency list

• I wanted to see if I could come up with an iterative way to check cycles, which as it turns out requires a modification to the traditional iterative DFS method. To make sure that I am detected back edges correctly, I store the current edge being explored from a vertex on its stack frame, and don't pop the node off the stack until it has explored all its edges. This is similar to what is going on in the call stack of recursive DFS.

``````class Solution(object):

class Vertex:
def __init__(self):
self.edges = []
self.visited = False
self.first_visited = False

def canFinish(self, numCourses, prerequisites):

verticies = [Solution.Vertex() for _ in range(numCourses)]
for prereq in prerequisites:
verticies[prereq[1]].edges.append(verticies[prereq[0]])

#Runs dfs
def hasCycle(v):
stack = [[v, 0]]
v.visited = True
v.first_visited = True

while len(stack):
curr = stack[-1][0]
nextEdge = stack[-1][1]
if nextEdge >= len(curr.edges): #we've visited all children
curr.visited = False
stack.pop()
continue
next = curr.edges[nextEdge]
if (next.visited):
return True
next.visited = True
next.first_visited = True
stack[-1][1] += 1
stack.append([next, 0])
return False

for v in verticies:
if not v.first_visited:
if hasCycle(v):
return False

return True``````

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