#.12 Write a program that implements Kruskal’s algorithm to generate minimum costs panning Tree.

class DisjointSet:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0] * n

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

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)

        if root_u != root_v:
            # Union by rank
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_u] < self.rank[root_v]:
                self.parent[root_u] = root_v
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1

class Graph:
    def __init__(self, vertices):
        self.V = vertices  
        self.edges = []    

    def add_edge(self, u, v, weight):
        self.edges.append((weight, u, v))

    def kruskal_mst(self):
       
        self.edges.sort()
               
        ds = DisjointSet(self.V)
        
        mst_edges = [] 
        total_weight = 0  
        
        for weight, u, v in self.edges:
          
            if ds.find(u) != ds.find(v):
                ds.union(u, v)  # Union the sets
                mst_edges.append((u, v, weight)) 
                total_weight += weight 
        
        return mst_edges, total_weight

# Example usage
if __name__ == "__main__":
    g = Graph(5)
    g.add_edge(0, 1, 10)
    g.add_edge(0, 2, 6)
    g.add_edge(0, 3, 5)
    g.add_edge(1, 3, 15)
    g.add_edge(2, 3, 4)

    mst, total_weight = g.kruskal_mst()
    print("Edges in the Minimum Spanning Tree:")
    for u, v, weight in mst:
        print(f"{u} -- {v} == {weight}")
    print("Total weight of the Minimum Spanning Tree:", total_weight)