Advertisement
Guest User

Untitled

a guest
Mar 30th, 2020
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.68 KB | None | 0 0
  1. def get_root(v):
  2. if v == root[v]:
  3. return v
  4. root[v] = get_root(root[v])
  5. return root[v]
  6.  
  7.  
  8. def U(a, b):
  9. a = get_root(a)
  10. b = get_root(b)
  11. if a != b:
  12. root[b] = a
  13.  
  14.  
  15. fi = open("spantree3.in", "r")
  16. fo = open("spantree3.out", "w")
  17.  
  18. n, m = [int(x) for x in fi.readline().split()]
  19.  
  20. g = []
  21.  
  22. for i in range(m):
  23. b, e, w = [int(x) for x in fi.readline().split()]
  24. g.append([w, [b-1, e-1]])
  25. g.sort()
  26.  
  27. root = [x for x in range(n)]
  28. res = 0
  29.  
  30. for i in range(m):
  31. w = g[i][0]
  32. b = g[i][1][0]
  33. e = g[i][1][1]
  34. if get_root(b) != get_root(e):
  35. res += w
  36. U(b, e)
  37.  
  38. print(res, file=fo)
  39.  
  40. fi.close()
  41. fo.close()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement