Advertisement
viligen

cheap_town_trip_Kruskal

Aug 9th, 2022
740
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.70 KB | None | 0 0
  1. def find_root(parent, node):
  2.     while node != parent[node]:
  3.         node = parent[node]
  4.     return node
  5.  
  6.  
  7. nodes = int(input())
  8. edges = int(input())
  9.  
  10. graph = []
  11.  
  12. for _ in range(edges):
  13.     first, second, weight = [ int(x) for x in input().split(' - ')]
  14.     graph.append((first, second, weight))
  15.  
  16. parent = [num for num in range(nodes)]
  17. total_cost = 0
  18.  
  19.  
  20.  
  21.  
  22. for first, second, weight in sorted(graph, key=lambda e: e[2]):
  23.     first_node_root = find_root(parent, first)
  24.     second_node_root = find_root(parent, second)
  25.  
  26.     if first_node_root == second_node_root:
  27.         continue
  28.     parent[first_node_root] = second_node_root
  29.     total_cost += weight
  30.  
  31. print(f'Total cost: {total_cost}')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement