Skip to content

Instantly share code, notes, and snippets.

@jakab922
Created June 24, 2018 21:12
Show Gist options
  • Save jakab922/94b157b6f9ddf9ab54eaa64e118b6eee to your computer and use it in GitHub Desktop.
Save jakab922/94b157b6f9ddf9ab54eaa64e118b6eee to your computer and use it in GitHub Desktop.
Circle check in a weighted directed graph
def circle_check(graph):
n = len(graph)
graph = [list(node.keys()) for node in graph]
indexes = [0] * n
stack = [0]
visited = [False] * n
visited[0] = True
while stack:
curr = stack[-1]
while stack and len(graph[curr]) == indexes[curr]:
visited[curr] = False
stack.pop()
if stack:
curr = stack[-1]
if not stack:
break
neigh = graph[curr][indexes[curr]]
indexes[curr] += 1
if visited[neigh]:
return True
visited[neigh] = True
stack.append(neigh)
return False
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment