Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def tarjan(V, E):
- i = 0
- S = []
- index = {}
- lowlink = {}
- stackset = set()
- components = []
- def strongconnect(v):
- nonlocal i
- index[v] = i
- lowlink[v] = i
- i += 1
- S.append(v)
- stackset.add(v)
- for w in E[v]:
- if w not in index:
- strongconnect(w)
- lowlink[v] = min(lowlink[v], lowlink[w])
- elif w in stackset:
- lowlink[v] = min(lowlink[v], index[w])
- if lowlink[v] == index[v]:
- component = []
- components.append(component)
- while True:
- w = S.pop()
- stackset.remove(w)
- component.append(w)
- if w == v:
- break
- for v in V:
- if v not in index:
- strongconnect(v)
- return components[::-1]
- N = int(input())
- successors = {}
- for i in range(N):
- line = input()
- successors[i] = [j for j, c in enumerate(line)
- if c == '1']
- vertices = range(N)
- components = tarjan(vertices, successors)
- last_component = components[-1]
- if 0 not in last_component:
- print("impossible")
- else:
- import itertools
- from collections import deque
- joined = list(itertools.chain(components[:-1]))
- last_component = deque(last_component)
- while last_component[-1] != 0:
- last_component.rotate(1)
- joined += list(last_component)
- print(*joined)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement