Created
June 24, 2018 21:12
-
-
Save jakab922/94b157b6f9ddf9ab54eaa64e118b6eee to your computer and use it in GitHub Desktop.
Circle check in a weighted directed graph
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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