Advertisement
Guest User

Untitled

a guest
Dec 9th, 2018
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.79 KB | None | 0 0
  1. import sys
  2. sys.setrecursionlimit(0x10000000)
  3.  
  4.  
  5. def add(a, b):
  6. g[a].append(b)
  7. g[b].append(a)
  8.  
  9.  
  10. def dfs(v, p):
  11. ans = False
  12. color[v] = 1
  13. path.append(v)
  14. for i in g[v]:
  15. if color[i] == -1:
  16. if dfs(i, v):
  17. ans = True
  18. elif color[i] == 1 and i != p:
  19. ans = True
  20. path.append(i)
  21. color[v] = 2
  22. return ans
  23.  
  24.  
  25. n = int(input())
  26. path = []
  27. g = []
  28. color = []
  29. for i in range(n):
  30. g.append([])
  31. color.append(-1)
  32. for i in range(n):
  33. l = list(map(int, input().split()))
  34. for j in range(i + 1, n):
  35. if (l[j] == 1):
  36. add(i, j)
  37. ans = True
  38. for i in range(n):
  39. if color[i] == -1:
  40. ans &= dfs(i, 1)
  41.  
  42. if ans:
  43. print("YES")
  44. else:
  45. print("NO")
  46. print(path)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement