Union-Find tối ưu và Kruskal tìm cây khung

Giới thiệu

Bài này học Union-Find nhanh bằng cây và hai mẹo nén. Mẹo này giúp Kruskal tìm đường nối rẻ nhất.

Kiến thức cần nhớ

Từ danh sách sang cây

• Mỗi nhóm là một cây, gốc cây là đại diện.
• Mỗi nút chỉ giữ con trỏ tới cha của nó.
• union chỉ nối gốc này sang gốc kia.
• Ví dụ đời thường: sáp nhập lớp chỉ cần đổi biển lớp trưởng.

Nén đường đi và hợp theo hạng

• Nén đường đi: lúc find thì nối thẳng mọi nút về gốc.
• Hợp theo hạng: cây nhỏ chui dưới gốc cây lớn.
• Mỗi gốc giữ con số hạng để so lớn nhỏ.
• Ví dụ đời thường: đường tắt mới mở thì lần sau đi nhanh.

# Union-Find có nén đường đi + hợp theo hạng
cha = {}  # nút -> cha
hang = {}  # gốc -> hạng
def find(x):
    if cha[x] != x:  # chưa tới gốc
        cha[x] = find(cha[x])  # nối thẳng về gốc
    return cha[x]
def union(a, b):
    ra, rb = find(a), find(b)  # tìm 2 gốc
    if ra == rb: return False  # đã cùng nhóm
    if hang[ra] < hang[rb]:  # cây nhỏ chui dưới
        ra, rb = rb, ra
    cha[rb] = ra  # nối gốc nhỏ vào gốc lớn
    if hang[ra] == hang[rb]:  # bằng hạng thì gốc mới cao thêm 1
        hang[ra] += 1
    return True

Thuật toán Kruskal

• Sắp xếp mọi cạnh theo trọng số tăng dần.
• Duyệt từng cạnh, chưa cùng nhóm thì nhận và gộp.
• Cùng nhóm rồi thì bỏ qua để tránh chu trình.
• Ví dụ đời thường: nối các trạm điện bằng ít dây nhất.

Ví dụ

• Input: tam giác cạnh 1, 2, 3 -> Output: nhận cạnh 1 và 2, tổng 3.
• Câu này cho thấy cạnh 3 bị loại vì tạo vòng tròn.
• Input: find hai lần trên nhánh sâu -> Output: lần 2 chỉ 1 bước.
• Câu này cho thấy nén đường đi phát huy tác dụng.

💻 Bài tập

Ngôn ngữ: C++. Nộp vào day-033/.

Bài 1: Union-Find tối ưu

class DSU {
 public:
  explicit DSU(int n);
  int  find(int x);          // nén đường đi
  bool unite(int a, int b);  // hợp theo rank, bằng rank thì gốc mới tăng rank 1
  int  size(int x);          // kích thước nhóm chứa x
  int  count() const;
};

Viết thêm find bản vòng lặp (không đệ quy) dùng kỹ thuật chia đôi đường đi (parent[x] = parent[parent[x]]).

Dãy xấu ngày 32 với n = 10^6 -> find(0) chạy tức thì, không tràn stack
unite(0,1); unite(2,3); unite(0,3) -> size(1) = 4

Chạy lại benchmark ngày 32 với DSU. In bảng 3 cách cài.

Bài 2: Kruskal

struct Edge { int u, v; long long w; };
std::pair<long long, std::vector<Edge>> kruskal(int n, std::vector<Edge> edges);

Đồ thị không liên thông thì trả rừng khung nhỏ nhất và in cảnh báo.

Tam giác (0,1,1) (1,2,2) (0,2,3)   -> tổng 3, nhận 2 cạnh đầu
n=4, cạnh (0,1,10) (0,2,6) (0,3,5) (1,3,15) (2,3,4) -> tổng 19
n=3, 1 cạnh (0,1,5)                -> rừng, tổng 5, cảnh báo không liên thông

Bài 3: Ứng dụng (nâng cao)

1. Đếm đảo: lưới '1'/'0' cỡ $1000 \times 1000$. Đếm số đảo bằng DSU (không dùng DFS).
2. Cạnh thừa: cho cây $n$ nút cộng thêm đúng 1 cạnh. Tìm cạnh gây chu trình xuất hiện cuối cùng trong input.
3. Gom cụm bằng Kruskal: cho 30 điểm 2D, chạy Kruskal nhưng dừng khi còn đúng 3 nhóm. In nhãn nhóm từng điểm.

cạnh thừa: [(1,2),(1,3),(2,3)] -> (2,3)

✅ Tiêu chí hoàn thành

• Test mẫu pass. Kết quả Kruskal khớp với Prim hoặc vét cạn trên đồ thị nhỏ ngẫu nhiên.
• Bảng so sánh 3 cách cài Union-Find có số thật.
• Giải thích được vì sao Kruskal cần Union-Find để phát hiện chu trình.
• Nêu độ phức tạp Kruskal: $O(E \log E)$.

❓ Câu hỏi ôn tập

• Vì sao biểu diễn cây giúp gộp nhanh hơn?
• Nén đường đi làm gì trong lúc tìm?
• Hợp theo hạng chọn cây nào làm gốc?
• Kruskal xét cạnh theo thứ tự nào?

🌕 Bạn đã hoàn thành ngày 33. Làm hết bài tập phía trên rồi sang ngày tiếp theo.