Cây khung nhỏ nhất (MST)

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank   = [0] * 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):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True


def kruskal_mst(n, canh):
    """
    Tìm MST bằng thuật toán Kruskal.

    n   : số đỉnh (0-indexed)
    canh: [(u, v, w)] — danh sách cạnh có trọng số
    Trả về: (tong_trong_so, danh_sach_canh_mst)
    """
    canh_sap_xep = sorted(canh, key=lambda e: e[2])
    dsu  = DSU(n)
    mst  = []
    tong = 0

    for u, v, w in canh_sap_xep:
        if dsu.union(u, v):
            mst.append((u, v, w))
            tong += w
            if len(mst) == n - 1:
                break    # Đủ V-1 cạnh rồi

    if len(mst) < n - 1:
        return -1, []    # Đồ thị không liên thông

    return tong, mst


# Đồ thị 5 đỉnh
canh = [(0,1,2),(0,3,6),(1,2,3),(1,3,8),(1,4,5),(2,4,7),(3,4,9)]
tong, mst = kruskal_mst(5, canh)
print(f"Tổng MST: {tong}")               # 16
print("Các cạnh MST:")
for u, v, w in mst:
    print(f"  {u} - {v}: {w}")

import heapq
from collections import defaultdict

def prim_mst(n, canh):
    """
    Tìm MST bằng thuật toán Prim.
    Xuất phát từ đỉnh 0.
    """
    graph = defaultdict(list)
    for u, v, w in canh:
        graph[u].append((w, v))
        graph[v].append((w, u))

    trong_mst = [False] * n
    min_heap  = [(0, 0, -1)]   # (trọng_số, đỉnh, đỉnh_cha)
    tong = 0
    mst  = []

    while min_heap and len(mst) < n:
        w, u, cha = heapq.heappop(min_heap)
        if trong_mst[u]:
            continue
        trong_mst[u] = True
        tong += w
        if cha != -1:
            mst.append((cha, u, w))

        for w2, v in graph[u]:
            if not trong_mst[v]:
                heapq.heappush(min_heap, (w2, v, u))

    if len(mst) < n - 1:
        return -1, []    # Không liên thông

    return tong, mst


canh = [(0,1,2),(0,3,6),(1,2,3),(1,3,8),(1,4,5),(2,4,7),(3,4,9)]
tong, mst = prim_mst(5, canh)
print(f"Tổng MST (Prim): {tong}")     # 16
for u, v, w in mst:
    print(f"  {u} - {v}: {w}")

def chi_phi_ket_noi_toi_thieu(n, ket_noi):
    """
    Tìm chi phí tối thiểu để kết nối n thành phố (đánh số 1..n).
    ket_noi: [(tp1, tp2, chi_phi)]
    Trả về -1 nếu không thể kết nối tất cả.
    """
    # Chuyển về 0-indexed
    canh = [(u-1, v-1, w) for u, v, w in ket_noi]

    class DSU_:
        def __init__(self, n):
            self.p = list(range(n))
        def find(self, x):
            if self.p[x] != x: self.p[x] = self.find(self.p[x])
            return self.p[x]
        def union(self, x, y):
            px, py = self.find(x), self.find(y)
            if px == py: return False
            self.p[px] = py; return True

    dsu  = DSU_(n)
    canh = sorted(canh, key=lambda e: e[2])
    tong = 0
    cnt  = 0
    for u, v, w in canh:
        if dsu.union(u, v):
            tong += w
            cnt  += 1
    return tong if cnt == n - 1 else -1

print(chi_phi_ket_noi_toi_thieu(4, [(1,2,3),(1,3,1),(2,3,4),(2,4,2),(3,4,5)]))  # 6
print(chi_phi_ket_noi_toi_thieu(3, [(1,2,1),(2,3,2)]))                          # 3
print(chi_phi_ket_noi_toi_thieu(4, [(1,2,1),(2,3,2)]))                          # -1 (không liên thông)

def mst_voi_canh_bat_buoc(n, canh_tu_do, canh_bat_buoc):
    """
    Tìm MST khi một số cạnh bắt buộc phải có.
    Chiến lược: Thêm cạnh bắt buộc trước, kiểm tra chu trình,
    rồi Kruskal cho cạnh còn lại.
    """
    class DSU_:
        def __init__(self, n):
            self.p, self.r = list(range(n)), [0]*n
        def find(self, x):
            if self.p[x]!=x: self.p[x]=self.find(self.p[x])
            return self.p[x]
        def union(self, x, y):
            px,py=self.find(x),self.find(y)
            if px==py: return False
            if self.r[px]<self.r[py]: px,py=py,px
            self.p[py]=px
            if self.r[px]==self.r[py]: self.r[px]+=1
            return True

    dsu  = DSU_(n)
    tong = 0
    cnt  = 0

    # Bước 1: Thêm cạnh bắt buộc
    for u, v, w in canh_bat_buoc:
        if not dsu.union(u, v):
            return -1, []    # Cạnh bắt buộc tạo chu trình → vô nghiệm
        tong += w
        cnt  += 1

    # Bước 2: Kruskal cho cạnh tự do
    for u, v, w in sorted(canh_tu_do, key=lambda e: e[2]):
        if dsu.union(u, v):
            tong += w
            cnt  += 1
    return (tong if cnt == n-1 else -1), cnt

canh_tu_do   = [(0,1,5),(0,2,3),(1,3,2),(2,3,4)]
canh_bat_buoc = [(1,2,10)]     # Phải có cạnh 1-2
tong, cnt = mst_voi_canh_bat_buoc(4, canh_tu_do, canh_bat_buoc)
print(f"Tổng: {tong}, Số cạnh: {cnt}")   # 17, 3

def max_spanning_tree(n, canh):
    """
    Tìm cây khung LỚN NHẤT.
    Trick: sắp xếp cạnh giảm dần thay vì tăng dần.
    """
    class DSU_:
        def __init__(self, n):
            self.p, self.r = list(range(n)), [0]*n
        def find(self, x):
            if self.p[x]!=x: self.p[x]=self.find(self.p[x])
            return self.p[x]
        def union(self, x, y):
            px,py=self.find(x),self.find(y)
            if px==py: return False
            if self.r[px]<self.r[py]: px,py=py,px
            self.p[py]=px
            if self.r[px]==self.r[py]: self.r[px]+=1
            return True

    canh_sap_xep = sorted(canh, key=lambda e: e[2], reverse=True)  # Giảm dần
    dsu  = DSU_(n)
    tong = 0
    cnt  = 0
    mst  = []
    for u, v, w in canh_sap_xep:
        if dsu.union(u, v):
            tong += w
            cnt  += 1
            mst.append((u,v,w))
    return (tong if cnt == n-1 else -1), mst

canh = [(0,1,2),(0,3,6),(1,2,3),(1,3,8),(1,4,5),(2,4,7),(3,4,9)]
tong, mst = max_spanning_tree(5, canh)
print(f"Tổng Max-ST: {tong}")  # 25
for e in mst: print(f"  {e}")