Chương 33 - Minimum Spanning Tree (MST)

MST = subset cạnh kết nối tất cả đỉnh với tổng trọng số min, không có chu trình. 2 thuật toán: Kruskal (sort edge + DSU) và Prim (heap grow từ 1 đỉnh). Cả 2 đều O(E log E).

Mục tiêu chương

Sau chương này, bạn sẽ:

• Cut property: cạnh nhỏ nhất qua cut → trong MST.
• Cycle property: cạnh lớn nhất trong cycle → KHÔNG trong MST.
• Kruskal (sort + DSU) vs Prim (heap grow) - chọn theo sparse/dense.
• LC 1697 và LC 1102 là MST-flavored: offline DSU sorting.

Khi nào dùng pattern này?

• Bài “kết nối tất cả N điểm/thành phố với cost min”.
• Bài “nâng cấp / xây mạng / pipe”.
• Hỏi cạnh critical / pseudo-critical → variant của MST.

Template code

# Kruskal: sort edges + DSU
def kruskal(n, edges):
    edges.sort(key=lambda e: e[2])
    dsu = DSU(n)
    total = 0
    for u, v, w in edges:
        if dsu.union(u, v):
            total += w
    return total


# Prim: heap-based grow
import heapq
def prim(n, graph):
    visited = [False] * n
    heap = [(0, 0)]                # (weight, node)
    total = 0
    while heap:
        w, u = heapq.heappop(heap)
        if visited[u]: continue
        visited[u] = True
        total += w
        for v, weight in graph[u]:
            if not visited[v]:
                heapq.heappush(heap, (weight, v))
    return total

Bài tự luyện cuối chương

• LC 1722 - Minimize Hamming Distance After Swap Operations
• LC 1971 - Find if Path Exists in Graph

---

33.1 Min Cost to Connect All Points (LC 1584)

Đề bài

Cho points 2D. Cost nối 2 điểm = Manhattan distance. Tìm cost min để nối tất cả.

Ví dụ

Input:  points = [[0,0], [2,2], [3,10], [5,2], [7,0]]
        (mỗi điểm [x, y]; cost giữa 2 điểm = |x1-x2| + |y1-y2| Manhattan)
Output: 20   (tổng cost MST nối tất cả điểm)

Ràng buộc

• 1 <= len(points) <= 1000
• -10^6 <= x, y <= 10^6

Clarifying questions

• n = 1? → Trả 0.
• Distance metric? → Theo đề: Manhattan.

Hướng tiếp cận

Kruskal: tạo tất cả O(n²) cạnh, sort, DSU. Prim: hợp lý hơn với dense graph (mỗi cặp đều có cạnh) - O(n²).

Code Python 3 (Prim)

import heapq
from typing import List

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        visited = [False] * n
        heap = [(0, 0)]
        total = 0
        count = 0
        while count < n:
            w, u = heapq.heappop(heap)
            if visited[u]: continue
            visited[u] = True
            total += w
            count += 1
            for v in range(n):
                if not visited[v]:
                    dist = abs(points[u][0]-points[v][0]) + abs(points[u][1]-points[v][1])
                    heapq.heappush(heap, (dist, v))
        return total

Phân tích độ phức tạp

• Prim O(n² log n). Có thể O(n²) với dense Prim (no heap).

Bình luận

• Bẫy: dùng matrix MST O(n²) thay vì heap khi graph dense.
• Follow-up: LC 1135 (Connecting Cities) - Kruskal.

Bài tự luyện liên quan

• LC 1135 - Connecting Cities (bài 33.2)
• LC 1168 - Optimize Water Distribution (bài 33.3)

---

33.2 Connecting Cities With Minimum Cost (LC 1135)

Đề bài

Cho cities 1..n và list connections[i] = [a, b, cost]. Min cost kết nối tất cả, hoặc -1 nếu không thể.

Ví dụ

Input:  n=3, connections=[[1,2,5],[1,3,6],[2,3,1]]
Output: 6

Ràng buộc

• 1 <= n <= 10^4
• 1 <= len(connections) <= 10^4

Clarifying questions

• Không thể connect tất cả? → Trả -1.

Hướng tiếp cận

Kruskal cơ bản. Sort tất cả cạnh theo trọng số tăng dần, dùng DSU để chỉ nhận cạnh nối 2 component khác nhau; sau khi duyệt hết, nếu DSU còn đúng 1 component thì trả về tổng trọng số.

Code Python 3

from typing import List

class Solution:
    def minimumCost(self, n: int, connections: List[List[int]]) -> int:
        connections.sort(key=lambda c: c[2])
        parent = list(range(n + 1))
        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        total = 0
        used = 0
        for a, b, c in connections:
            ra, rb = find(a), find(b)
            if ra != rb:
                parent[ra] = rb
                total += c
                used += 1
                if used == n - 1:
                    return total
        return -1

Phân tích độ phức tạp

• Thời gian: O(E log E) (Kruskal sort).
• Bộ nhớ: O(V).

Bình luận

• Bẫy: quên check graph có thể không liên thông → trả -1.
• Follow-up: LC 1168 (Optimize Water) - virtual node trick.

Bài tự luyện liên quan

• LC 1584 - Min Cost to Connect All Points (bài 33.1)
• LC 1489 - Critical Edges (bài 33.4)

---

33.3 Optimize Water Distribution in a Village (LC 1168)

Đề bài

n nhà. Mỗi nhà có thể: (a) đào giếng riêng cost wells[i], hoặc (b) nối ống với nhà khác pipes[j] = [u, v, c]. Min total cost cấp nước cho tất cả.

Ví dụ

Input:  n=3, wells=[1,2,2], pipes=[[1,2,1],[2,3,1]]
Output: 3

Ràng buộc

• 1 <= n <= 10^4
• wells.length == n

Clarifying questions

• Pipes có self-loop? → Không hợp lệ; skip.

Hướng tiếp cận

Trick virtual node 0: thêm node 0 và cạnh (0, i, wells[i]) cho mỗi nhà. Sau đó MST trên n+1 đỉnh.

Code Python 3

from typing import List

class Solution:
    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:
        edges = pipes[:]
        for i, w in enumerate(wells):
            edges.append([0, i + 1, w])
        edges.sort(key=lambda e: e[2])
        parent = list(range(n + 1))
        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x
        total = 0
        for u, v, c in edges:
            ru, rv = find(u), find(v)
            if ru != rv:
                parent[ru] = rv
                total += c
        return total

Phân tích độ phức tạp

• Thời gian: O((V + E) log E).
• Bộ nhớ: O(V + E).

Bình luận

• Pattern “virtual node” - chuyển bài có “self-option” thành MST chuẩn.

Bài tự luyện liên quan

• LC 1135 - Connecting Cities (bài 33.2)
• LC 1722 - Minimize Hamming Distance After Swap

---

33.4 Critical and Pseudo-Critical Edges in MST (LC 1489)

Đề bài

Input: n (số đỉnh) và edges: List[List[int]] - mỗi cạnh [u, v, w] là cạnh vô hướng có trọng số w. Tìm tất cả critical edges (xoá → MST cost tăng) và pseudo-critical (có thể xuất hiện trong some MST).

Ví dụ

Input:  n=5, edges=[[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
Output: [[0,1],[2,3,4,5]]

Ràng buộc

• 2 <= n <= 100
• 1 <= len(edges) <= min(200, n·(n-1)/2)

Clarifying questions

• Multi-edge có cùng cost? → Pseudo-critical tự nhiên xuất hiện.

Hướng tiếp cận

1. Tính mst_cost ban đầu.
2. Với mỗi edge e:
   • Skip e → tính MST còn lại. Nếu không thể hoặc cost > mst_cost → e critical.
   • Force e (union trước) → tính MST. Nếu cost == mst_cost → e pseudo-critical hoặc critical.

Code Python 3

from typing import List

class Solution:
    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        # Đánh nhãn index để track sau khi sort.
        indexed = [e + [i] for i, e in enumerate(edges)]
        indexed.sort(key=lambda e: e[2])

        def kruskal(skip=-1, force=-1) -> int:
            parent = list(range(n))
            def find(x):
                while parent[x] != x:
                    parent[x] = parent[parent[x]]
                    x = parent[x]
                return x
            total = used = 0
            if force != -1:
                u, v, w, _ = indexed[force]
                parent[find(u)] = find(v)
                total = w
                used = 1
            for i, (u, v, w, _) in enumerate(indexed):
                if i == skip or i == force: continue
                ru, rv = find(u), find(v)
                if ru != rv:
                    parent[ru] = rv
                    total += w
                    used += 1
            return total if used == n - 1 else float('inf')

        base = kruskal()
        critical, pseudo = [], []
        for i, (u, v, w, orig) in enumerate(indexed):
            if kruskal(skip=i) > base:
                critical.append(orig)
            elif kruskal(force=i) == base:
                pseudo.append(orig)
        return [critical, pseudo]

Phân tích độ phức tạp

• Thời gian: O(E² · α(V)) worst (mỗi edge thử skip + force).
• Bộ nhớ: O(V + E).

Bình luận

• Bài Hard tiêu biểu - nhận ra “MST đủ để giải” là chìa khoá; sau đó vấn đề quy về kiểm tra từng cạnh có thuộc MST tối ưu hay không.

Bài tự luyện liên quan

• LC 1135 - Connecting Cities
• LC 1697 - Edge Length Limited Paths (bài 33.5)

---

33.5 Checking Existence of Edge Length Limited Paths (LC 1697)

Đề bài

Cho graph vô hướng với edgeList[i] = [u, v, dist] và mảng queries[j] = [p, q, limit]. Với mỗi query, trả về True nếu tồn tại path giữa p, q mà mọi cạnh trên path có dist < limit.

Ví dụ

Input:  n=3, edges=[[0,1,2],[1,2,4],[2,0,8],[1,0,16]]
        queries=[[0,1,2],[0,2,5]]
Output: [False, True]

Ràng buộc

• 2 <= n <= 10^5
• 1 <= edgeList.length <= 10^5

Clarifying questions

• Cạnh dist == limit có hợp lệ không? → Không (đề dùng <).
• Multi-edge? → Có thể, lấy edge có dist nhỏ nhất là đủ.

Hướng tiếp cận

Brute force: BFS/DFS mỗi query với điều kiện dist < limit. O(Q · E). TLE.

Tối ưu - Offline Kruskal-style - O((E + Q) log).

Sort cả edgeList (theo dist) và queries (theo limit). Duyệt queries tăng: với mỗi query, union tất cả edge có dist < limit vào DSU. Sau đó check find(p) == find(q).

Code Python 3

from typing import List

class Solution:
    def distanceLimitedPathsExist(self, n: int, edgeList: List[List[int]],
                                   queries: List[List[int]]) -> List[bool]:
        parent = list(range(n))
        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x
        def union(x: int, y: int) -> None:
            rx, ry = find(x), find(y)
            if rx != ry:
                parent[rx] = ry

        edgeList.sort(key=lambda e: e[2])
        # Thêm index gốc của query để output đúng thứ tự.
        indexed_q = sorted(enumerate(queries), key=lambda kv: kv[1][2])

        result = [False] * len(queries)
        i = 0
        for q_idx, (p, q, limit) in indexed_q:
            while i < len(edgeList) and edgeList[i][2] < limit:
                u, v, _ = edgeList[i]
                union(u, v)
                i += 1
            result[q_idx] = (find(p) == find(q))
        return result

Phân tích độ phức tạp

• Thời gian: O((E + Q) log (E + Q) + (E + Q) · α(n)).
• Bộ nhớ: O(n + Q).

Bình luận

• Pattern “offline DSU sorting” là biến thể của Kruskal - sort cạnh theo trọng số rồi union dần. Khác với MST gốc ở chỗ ta xử lý song song với queries.
• Bẫy: dùng < (strict) theo đề; nếu đề bài cho <= thì đổi điều kiện.

Bài tự luyện liên quan

• LC 1101 - The Earliest Moment When Everyone Become Friends.
• LC 1631 - Path With Minimum Effort.

---

33.6 Path With Maximum Minimum Value (LC 1102)

Đề bài

Grid m × n. Tìm path từ (0,0) đến (m-1,n-1) (4 hướng) sao cho giá trị min trên path là max có thể. Trả về giá trị đó.

Ví dụ

Input:  grid = [[5, 4, 5],
                [1, 2, 6],
                [7, 4, 6]]   (grid m × n, đi 4 hướng từ (0,0) → (m-1, n-1))
Output: 4   (giá trị MIN gặp phải trên path tốt nhất đạt cực đại = 4)   (path 5→4→5→6→6 có min = 4)

Ràng buộc

• 1 <= m, n <= 100
• 0 <= grid[i][j] <= 10^9

Clarifying questions

• Path qua mỗi ô tối đa 1 lần? → Theo đề: có.
• Path có cần đi qua cả 2 góc không? → Có, bắt đầu (0,0), kết thúc (m-1,n-1).

Hướng tiếp cận

Pattern “Kruskal ngược” - kích hoạt ô theo giá trị giảm dần. Khi (0,0) và (m-1,n-1) cùng component → giá trị ô vừa kích hoạt là đáp án (vì nó là min trên path tìm được).

Bài này cùng pattern với Swim in Rising Water (Ch 24.6) nhưng đảo chiều: thay vì “elevation thấp nhất activate trước” → “value cao nhất activate trước”.

Code Python 3

from typing import List

class Solution:
    def maximumMinimumPath(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        parent = list(range(m * n))
        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x
        def union(x: int, y: int) -> None:
            rx, ry = find(x), find(y)
            if rx != ry:
                parent[rx] = ry

        # Sort cells theo value GIẢM dần.
        cells = sorted(
            ((grid[r][c], r, c) for r in range(m) for c in range(n)),
            reverse=True,
        )
        active = [[False] * n for _ in range(m)]
        DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        for val, r, c in cells:
            active[r][c] = True
            idx = r * n + c
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and active[nr][nc]:
                    union(idx, nr * n + nc)
            if find(0) == find(m * n - 1):
                return val
        return -1

Phân tích độ phức tạp

• Thời gian: O(mn · log(mn) + mn · α).
• Bộ nhớ: O(mn).

Bình luận

• Pattern “offline DSU theo thứ tự giá trị” áp được cho mọi bài “max-min path” hoặc “min-max path”.
• Cách khác - Binary search trên answer: binary search giá trị v, BFS qua các ô có grid[r][c] >= v. O(log(max) · mn). Xem Ch 37 cho pattern này.

Bài tự luyện liên quan

• LC 778 - Swim in Rising Water.
• LC 1631 - Path With Minimum Effort.

Tóm tắt chương & Quyết định

MST proof principles

• Cut property: với mọi cut, cạnh trọng số nhỏ nhất băng qua cut nằm trong một MST nào đó.
• Cycle property: trong mọi cycle, cạnh trọng số lớn nhất không nằm trong bất kỳ MST nào.
• Hệ quả: Kruskal (chọn cạnh tăng dần) và Prim (mở rộng từ 1 node) đều build MST đúng.

Kruskal vs Prim

	Kruskal	Prim
Cấu trúc dữ liệu	DSU + sort edges	Heap + visited
Time	O(E log E)	O(E log V)
Đồ thị thưa	✅ Tốt	OK
Đồ thị dày	OK	✅ Tốt hơn
Cần edge list	✅	Cần adjacency list
Streaming edges	✅ (xử lý tăng dần)	❌

Kruskal mental model

“Sort cạnh theo trọng số → mỗi cạnh, nếu nối 2 component khác nhau, lấy. DSU theo dõi connectivity dần dần.”

LC 1697 - Offline connectivity threshold (KHÔNG phải MST nhưng cùng họ)

• Sort cả edges và queries theo trọng số.
• Duyệt query theo limit tăng dần, union mọi cạnh < limit ⇒ trả lời “u, v có cùng component?” bằng DSU.
• Đây là Kruskal logic áp dụng cho threshold query.

Path Maximum Minimum / Bottleneck path

• Tương đương “tìm path mà cạnh min dọc path lớn nhất”.
• Cách 1: Kruskal-style (sort cạnh giảm, union cho đến khi src ↔︎ dst cùng comp).
• Cách 2: Dijkstra max-min thay vì sum (relax với min(d, edge)).

---