Kruskal

class DisjointSet:
def init(self, n):
self.parent = [i for i in range(n)]

def find(self, x):
    if self.parent[x] != x:
        self.parent[x] = self.find(self.parent[x])  
    return self.parent[x]

def union(self, x, y):
    rootX = self.find(x)
    rootY = self.find(y)
    if rootX != rootY:
        self.parent[rootY] = rootX
        return True
    return False

def kruskal(n, edges):
dsu = DisjointSet(n)
mst = []
edges.sort()

print("\nEdge : Weight")
for weight, u, v in edges:
    if dsu.union(u, v):
        mst.append((u, v, weight))
        print(f"{u} - {v} : {weight}")

n = int(input("Enter number of vertices: "))
e = int(input("Enter number of edges: "))

edges = []
print("Enter each edge in the format: u v weight")
for _ in range(e):
u, v, w = map(int, input().split())
edges.append((w, u, v))

kruskal(n, edges)