Advertisement
serega1112

Postroenie

Feb 19th, 2022
959
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.76 KB | None | 0 0
  1. from collections import defaultdict
  2.  
  3. n, m = map(int, input().split())
  4. g = defaultdict(set)
  5. for i in range(m):
  6.     a, b = map(int, input().split())
  7.     g[a].add(b)
  8.  
  9. topsort = []
  10. res = True
  11. visited = [0] * 101
  12.  
  13. def dfs(node):
  14.     if not visited[node]:
  15.         visited[node] = 1
  16.         res = True
  17.         for neigh in g[node]:
  18.             res = res and dfs(neigh)
  19.         visited[node] = 2
  20.         topsort.append(node)
  21.         return res
  22.     elif visited[node] == 1:
  23.         return False
  24.     else:
  25.         return True
  26.  
  27. for v in range(1, n+1):
  28.     if not visited[v]:
  29.         if not dfs(v):
  30.             res = False
  31.             break
  32.  
  33. if res:
  34.     print("Yes")
  35.     print(' '.join([str(item) for item in reversed(topsort)]))
  36. else:
  37.     print("No")
  38.  
  39.  
  40.  
  41.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement