Advertisement
sweeneyde

Untitled

Dec 13th, 2020
739
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.49 KB | None | 0 0
  1. def tarjan(V, E):
  2.     i = 0
  3.     S = []
  4.     index = {}
  5.     lowlink = {}
  6.     stackset = set()
  7.     components = []
  8.  
  9.     def strongconnect(v):
  10.         nonlocal i
  11.         index[v] = i
  12.         lowlink[v] = i
  13.         i += 1
  14.         S.append(v)
  15.         stackset.add(v)
  16.  
  17.         for w in E[v]:
  18.             if w not in index:
  19.                 strongconnect(w)
  20.                 lowlink[v] = min(lowlink[v], lowlink[w])
  21.             elif w in stackset:
  22.                 lowlink[v] = min(lowlink[v], index[w])
  23.  
  24.         if lowlink[v] == index[v]:
  25.             component = []
  26.             components.append(component)
  27.             while True:
  28.                 w = S.pop()
  29.                 stackset.remove(w)
  30.                 component.append(w)
  31.                 if w == v:
  32.                     break
  33.  
  34.     for v in V:
  35.         if v not in index:
  36.             strongconnect(v)
  37.  
  38.     return components[::-1]
  39.  
  40.  
  41. N = int(input())
  42. successors = {}
  43. for i in range(N):
  44.     line = input()
  45.     successors[i] = [j for j, c in enumerate(line)
  46.                     if c == '1']
  47.  
  48. vertices = range(N)
  49. components = tarjan(vertices, successors)
  50. last_component = components[-1]
  51. if 0 not in last_component:
  52.     print("impossible")
  53. else:
  54.     import itertools
  55.     from collections import deque
  56.  
  57.     joined = list(itertools.chain(components[:-1]))
  58.     last_component = deque(last_component)
  59.     while last_component[-1] != 0:
  60.         last_component.rotate(1)
  61.  
  62.     joined += list(last_component)
  63.     print(*joined)
  64.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement