Dùng Union–Find để theo dõi nhóm lớp liên kết

1. Mô hình quan hệ dưới dạng liên thông

Nếu hai lớp có người học chung, ta thêm một cạnh vô hướng giữa chúng. Các thành phần liên thông cho biết nhóm lớp được nối qua chuỗi cạnh. Hai lớp cùng nhóm chưa chắc xung đột trực tiếp, nên không thể dùng quan hệ cùng nhóm để cấm mọi cặp lớp học cùng giờ.

2. Chọn đại diện và gộp nhóm

Mỗi đỉnh bắt đầu làm cha của chính nó. Tìm đại diện bằng cách đi theo liên kết cha. Khi tìm, có thể nén đường đi để những lần sau đi ít bước hơn. Khi gộp, nối gốc của nhóm nhỏ hơn vào gốc nhóm lớn hơn. Hai thao tác giúp truy vấn liên thông nhanh qua một chuỗi cập nhật thêm cạnh.

3. Theo dõi số cụm trong ví dụ

Bốn lớp A, B, C và D. Gộp A–B và B–C thì A cùng nhóm C, còn D riêng. Gộp A–C lần nữa không làm giảm số cụm. Cuối cùng gộp C–D thì còn một nhóm. Mã kiểm tra từng bước thay vì chỉ xem kết quả cuối, để bắt lỗi đếm trùng khi hai đỉnh đã cùng đại diện.

Chạy ví dụ bằng python gt_union_find_cum_lop.py.

class Nhom:
    def __init__(self, lop):
        self.cha = {x: x for x in lop}
        self.co = dict.fromkeys(self.cha, 1)
        self.so_nhom = len(self.cha)

    def goc(self, x):
        while self.cha[x] != x:
            self.cha[x] = self.cha[self.cha[x]]
            x = self.cha[x]
        return x

    def gop(self, a, b):
        a, b = self.goc(a), self.goc(b)
        if a == b:
            return
        if self.co[a] < self.co[b]:
            a, b = b, a
        self.cha[b] = a
        self.co[a] += self.co[b]
        self.so_nhom -= 1

nhom = Nhom("ABCD")
nhom.gop("A", "B")
nhom.gop("B", "C")
assert nhom.goc("A") == nhom.goc("C") != nhom.goc("D")
nhom.gop("A", "C")
assert nhom.so_nhom == 2
nhom.gop("C", "D")
assert nhom.so_nhom == 1
print("Còn một nhóm sau khi nối C với D.")

4. Đặt giới hạn của phép cập nhật

Xóa một cạnh có thể tách nhóm hoặc giữ nhóm nếu còn đường thay thế. Union–Find cơ bản không lưu đủ cấu trúc để quyết định điều đó. Với ít lần xóa, dựng lại từ danh sách cạnh hiện hành có thể đủ. Khi đánh giá giải pháp, tách chi phí thêm cạnh, truy vấn và dựng lại khỏi nhau.

Đọc thêm Tài liệu giải thuật của Princeton.