Advertisement
Griwin

Untitled

Dec 5th, 2022
46
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.17 KB | None | 0 0
  1. import math
  2. import os
  3. import random
  4. import re
  5. import sys
  6. sys.setrecursionlimit(10**5)
  7. def parent(n, st): # Fn to find set representative
  8. if n == st[n]:
  9. return n
  10. p = parent(st[n], st)
  11. st[n] = p # path compression
  12. return p
  13.  
  14. def kruskals(n, f, t, w):
  15. # Cases given for equal edge wt dont matter
  16. conn = []
  17. for i in range(len(f)):
  18. conn.append([w[i], f[i]-1, t[i]-1])
  19. conn.sort() # sort by edge weight
  20. s = [i for i in range(n)] # disjoint set
  21. ans = 0
  22. for wt, e1, e2 in conn:
  23. if parent(e1, s) != parent(e2, s): # If nodes are of different sets (no cycle)
  24. ans += wt
  25. s[parent(e1, s)] = parent(e2, s)
  26. print(ans)
  27. return str(ans)
  28.  
  29. if __name__ == '__main__':
  30. fptr = open(os.environ['OUTPUT_PATH'], 'w')
  31. g_nodes, g_edges = map(int, input().rstrip().split())
  32. g_from = [0] * g_edges
  33. g_to = [0] * g_edges
  34. g_weight = [0] * g_edges
  35. for i in range(g_edges):
  36. g_from[i], g_to[i], g_weight[i] = map(int, input().rstrip().split())
  37. res = kruskals(g_nodes, g_from, g_to, g_weight)
  38. # Write your code here.
  39. fptr.write(res + '\n')
  40. fptr.close()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement