Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- graph = []
- color = []
- answers = []
- count_v = 0
- def dfs(u):
- if color[u] == 2:
- return True
- color[u] = 1
- for v in graph[u]:
- if color[v] == 0:
- if not dfs(v):
- return False
- if color[v] == 1:
- return False
- color[u] = 2
- answers.append(u)
- return True
- def top_sort():
- for i in range(1, count_v + 1):
- if not dfs(i):
- return [-1]
- return list(reversed(answers))
- with open('input.txt', 'r') as fin:
- count_v, count_e = list(map(int, fin.readline().split()))
- graph = [[] for _ in range(count_v + 1)]
- color = [0 for _ in range(count_v + 1)]
- for _ in range(count_e):
- e1, e2 = list(map(int, fin.readline().split()))
- graph[e1].append(e2)
- with open('output.txt', 'w') as fout:
- ans = top_sort()
- for idx, vertex in enumerate(ans):
- fout.write(str(vertex))
- if idx != len(ans) - 1:
- fout.write(' ')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement