Union-find (tập hợp rời nhau - DSU): cách hoạt động, code và độ phức tạp

Union-find giải quyết vấn đề gì

Hãy tưởng tượng một mạng máy tính nơi các sợi cáp được thêm từng cái một, và sau mỗi sợi bạn phải trả lời "máy A và máy B có được kết nối không?". Chạy tìm kiếm đồ thị cho mỗi câu hỏi tốn O(n + m) mỗi lần. Union-find trả lời mỗi câu hỏi trong gần O(1) bằng cách duy trì các nhóm liên thông khi cáp được thêm vào.

Nhu cầu tương tự xuất hiện trong thuật toán cây khung nhỏ nhất Kruskal (hai đầu mút này đã thuộc cùng một cây chưa?), trong phát hiện chu trình ở đồ thị vô hướng, trong gom các tài khoản dùng chung một email, trong mô phỏng thấm (percolation), và trong xử lý ảnh để gán nhãn các vùng liên thông.

Ý tưởng giải thích đơn giản

Mỗi phần tử trỏ tới một cha. Phần tử trỏ vào chính nó là gốc, và gốc là đại diện của cả nhóm. Để tìm nhóm của x, đi theo các con trỏ cha cho tới khi gặp gốc. Để gộp hai nhóm, tìm cả hai gốc và cho một gốc trỏ tới gốc kia.

Hai tối ưu hóa giữ cho các cây luôn phẳng:

• Hợp theo hạng (hoặc theo kích thước): gắn cây thấp hơn (hoặc nhỏ hơn) dưới cây cao hơn (hoặc lớn hơn), nên chiều cao cây chỉ tăng khi hai cây bằng nhau được gộp.
• Nén đường đi: trong find, cho mọi node trên đường đi trỏ thẳng tới gốc, nên lần tra sau chỉ mất một bước.

Ví dụ minh họa: năm phần tử

Bắt đầu với các phần tử 0 đến 4, mỗi phần tử một nhóm. Mảng cha là [0, 1, 2, 3, 4]. Ta dùng hợp theo kích thước và cho gốc thứ hai làm con khi kích thước bằng nhau.

Cài đặt bằng Python

Phiên bản này dùng hợp theo kích thước và find dạng lặp với nén đường đi, nên không gặp vấn đề độ sâu đệ quy. union trả về False khi hai phần tử đã ở cùng một nhóm, điều này hữu ích để phát hiện chu trình.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.groups = n

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:       # path compression
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                    # already connected
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra                 # ra is the larger root
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.groups -= 1
        return True

    def connected(self, a, b):
        return self.find(a) == self.find(b)

uf = UnionFind(5)
uf.union(0, 1)
uf.union(2, 3)
uf.union(1, 3)
print(uf.find(3), uf.parent)       # 0 [0, 0, 0, 0, 4]
print(uf.connected(1, 4), uf.groups)  # False 2

Ví dụ: phát hiện chu trình trong đồ thị vô hướng

Xử lý từng cạnh một. Nếu cả hai đầu mút của một cạnh đã có cùng gốc, cạnh đó đóng thành một chu trình. Thuật toán Kruskal dùng đúng phép kiểm tra này sau khi sắp xếp các cạnh theo trọng số.

def has_cycle(n, edges):
    uf = UnionFind(n)
    for a, b in edges:
        if not uf.union(a, b):
            return True
    return False

print(has_cycle(4, [(0, 1), (1, 2), (2, 3)]))  # False
print(has_cycle(4, [(0, 1), (1, 2), (2, 0)]))  # True

Độ phức tạp thời gian và không gian

α(n) là hàm Ackermann nghịch đảo, tăng chậm đến mức không quá 4 với mọi n có thể đặt vừa trong một máy tính thực. Trên thực tế điều này nghĩa là thời gian hằng số cho mỗi thao tác. Robert Tarjan đã chứng minh chặn này vào năm 1975. Không gian là O(n) cho các mảng cha và kích thước.

Các biến thể và lỗi thường gặp

• So sánh phần tử thay vì gốc: union phải nối find(a) và find(b), không phải chính a và b.
• Cho rằng parent[x] là đại diện. Sau các lần union, chỉ find(x) mới đúng; hãy gọi find trên mọi phần tử trước khi nhóm theo cha.
• find đệ quy trên đầu vào lớn mà không hợp theo hạng có thể chạm giới hạn đệ quy của Python; phiên bản lặp ở trên tránh được điều này.
• Phần tử không phải số nguyên từ 0 đến n-1: hãy ánh xạ chúng sang chỉ số bằng dict trước, hoặc lưu cha trong một dict và thêm phần tử theo kiểu lười (lazy).
• Union-find không thể tách nhóm. Nếu các cạnh bị xóa, bạn cần một cấu trúc khác hoặc cách tiếp cận ngoại tuyến xử lý các thao tác xóa theo thứ tự ngược.
• Union-find có trọng số lưu một độ lệch tới cha trên mỗi node, trả lời được các câu như "a nặng hơn b bao nhiêu?".

Khi nào dùng và các bài toán điển hình

Dùng union-find khi các nhóm chỉ ngày càng gộp lại và bạn cần hỏi hai phần tử có cùng nhóm không, hoặc có bao nhiêu nhóm. Với một câu hỏi liên thông đơn lẻ trên đồ thị tĩnh, BFS hoặc DFS thông thường đơn giản hơn. Khi cần đường đi thực sự, hãy dùng tìm kiếm đồ thị, vì union-find chỉ biết tư cách thành viên.

Các bài toán điển hình: số thành phần liên thông, số hòn đảo (với ô lưới là phần tử), cạnh dư thừa (cạnh tạo ra chu trình), gộp tài khoản, tính thỏa mãn của các phương trình đẳng thức như a == b, b != c, và cây khung nhỏ nhất Kruskal.