Advertisement
jusohatam

Untitled

Nov 3rd, 2020
2,170
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.64 KB | None | 0 0
  1. def solution(n, graph):
  2.     def dfs(s):
  3.         visited = [0] * (n + 1)
  4.         s = [s]
  5.         while s:
  6.             u = s.pop()
  7.             if not visited[u]:
  8.                 visited[u] = 1
  9.                 s.extend(sorted(graph[u], reverse=True))
  10.         return visited[1:]
  11.  
  12.     for v in range(1, n+1):
  13.         visited = dfs(v)
  14.         for i in visited:
  15.             if not i:
  16.                 return False
  17.     return True
  18.  
  19.  
  20. n, m = map(int, input().split())
  21. graph = [[] for _ in range(n+1)]
  22. for _ in range(m):
  23.     i, j = map(int, input().split())
  24.     graph[i].append(j)
  25. if solution(n, graph):
  26.     print('YES')
  27. else:
  28.     print('NO')
  29.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement