Advertisement
Guest User

Untitled

a guest
Jan 20th, 2020
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.98 KB | None | 0 0
  1. graph = []
  2. color = []
  3. answers = []
  4. count_v = 0
  5.  
  6. def dfs(u):
  7.     if color[u] == 2:
  8.         return True
  9.     color[u] = 1
  10.     for v in graph[u]:
  11.         if color[v] == 0:
  12.             if not dfs(v):
  13.                 return False
  14.         if color[v] == 1:
  15.             return False
  16.     color[u] = 2
  17.     answers.append(u)
  18.     return True
  19.  
  20.  
  21. def top_sort():
  22.     for i in range(1, count_v + 1):
  23.         if not dfs(i):
  24.             return [-1]
  25.     return list(reversed(answers))
  26.  
  27.  
  28. with open('input.txt', 'r') as fin:
  29.     count_v, count_e = list(map(int, fin.readline().split()))
  30.     graph = [[] for _ in range(count_v + 1)]
  31.     color = [0 for _ in range(count_v + 1)]
  32.     for _ in range(count_e):
  33.         e1, e2 = list(map(int, fin.readline().split()))
  34.         graph[e1].append(e2)
  35.  
  36. with open('output.txt', 'w') as fout:
  37.     ans = top_sort()
  38.     for idx, vertex in enumerate(ans):
  39.         fout.write(str(vertex))
  40.         if idx != len(ans) - 1:
  41.             fout.write(' ')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement