Advertisement
Guest User

Untitled

a guest
Oct 14th, 2019
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.98 KB | None | 0 0
  1. def dfs(s):
  2. used[s] = 1
  3. que.append(s)
  4.  
  5. while len(que) != 0:
  6.  
  7. v = que[0]
  8. que.remove(v)
  9. y = True
  10. k = 0
  11. if v not in com2 and v not in com1:
  12. com1.append(v)
  13. elif v in com2:
  14. y = False
  15. for i in g[v]:
  16.  
  17.  
  18. if not used[i]:
  19. if y:
  20. com2.append(i)
  21. else:
  22. com1.append(i)
  23. used[i] = 1
  24. que.append(i)
  25.  
  26.  
  27. n = int(input())
  28. g = dict()
  29. for i in range(n):
  30.  
  31. mas = [int(x) for x in input().split()]
  32.  
  33. for j in mas:
  34.  
  35. if j != 0:
  36. if i + 1 not in g:
  37. g[i + 1] = set()
  38. if j not in g:
  39. g[j] = set()
  40.  
  41. g[i + 1].add(j)
  42. g[j].add(i + 1)
  43.  
  44. used = [0] * (n + 1)
  45. que = []
  46. maxk = -1
  47. com1 = []
  48. com2 = []
  49. for i in range(1, n + 1):
  50.  
  51. if not used[i]:
  52. dfs(i)
  53.  
  54. print(len(com1))
  55. print(*com1)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement