Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- topsort():
- cycle = False
- for i in range(n):
- cycle = dfs(i)
- if cycle:
- return false
- for i in range(n):
- numbers[stack.pop()] = i
- return true
- dfs (v):
- if color[v] == 1:
- return true
- if color[v] == 2:
- return false
- color[v] = 1;
- for i in range(len(edges[v])):
- if dfs(edges[v][i]):
- return True
- stack.append(v)
- color[v] = 2
- return False
- n = int(input()) # число вершин
- edges = [list() for i in range(n)]
- m = int(input()) # число рёбер
- for i in range(m):
- a, b = list(map(int, input().split()))
- edges[a].append(b)
- stack = list()
- numbers = [-1 for i in range(n)]
- color = [0 for i in range(n)]
- topsort()
- print(numbers)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement