Advertisement
viligen

MST_Kruskal

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