Minimum Spanning Tree — Kruskal's (Union-Find), Prim's (priority queue)

class DSU:
    def __init__(self, n):
        self.p = list(range(n))
        self.r = [0]*n                 # rank ~ tree height
    def find(self, x):
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]   # path compression (halving)
            x = self.p[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False      # already connected -> would make cycle
        if self.r[ra] < self.r[rb]: ra, rb = rb, ra
        self.p[rb] = ra
        if self.r[ra] == self.r[rb]: self.r[ra] += 1
        return True
 
def kruskal(n, edges):                 # edges: list of (w,u,v)
    dsu = DSU(n); total = 0; mst = []
    for w,u,v in sorted(edges):        # WHY sort: process lightest first (greedy)
        if dsu.union(u,v):             # WHY: union returns False if same component
            total += w; mst.append((u,v,w))
            if len(mst) == n-1: break  # WHY: a tree on n nodes needs exactly n-1 edges
    return total, mst

def prim(n, adj, start=0):             # adj[u] = list of (w,v)
    import heapq
    visited = [False]*n
    pq = [(0, start)]                  # (edge weight to reach node, node)
    total = 0; cnt = 0
    while pq and cnt < n:
        w, u = heapq.heappop(pq)       # WHY heap: pop the globally cheapest frontier edge
        if visited[u]: continue        # WHY: lazy deletion — stale heap entries skipped
        visited[u] = True; total += w; cnt += 1
        for ew, v in adj[u]:
            if not visited[v]:
                heapq.heappush(pq, (ew, v))   # WHY: v is now reachable across the cut
    return total