Tổng quan
Union-Find, còn gọi là Disjoint Set Union (DSU) hay tập rời rạc, là cấu trúc dữ liệu theo dõi một tập phần tử được phân hoạch thành các tập không giao nhau. Nó trả lời nhanh hai câu hỏi: một phần tử thuộc tập nào, và hai phần tử có cùng tập không?
Mỗi tập là một cây có gốc làm đại diện. Hai tối ưu hóa — hợp theo hạng (union by rank) và nén đường (path compression) — làm phẳng các cây này mạnh đến mức mỗi thao tác chạy gần như hằng số theo phân bổ.
Union-Find (DSU) hoạt động thế nào?
- Bắt đầu với mỗi phần tử là một tập đơn lẻ, tự trỏ đến chính mình làm cha.
- find(x) đi theo con trỏ cha lên tới gốc; nén đường trỏ lại mọi nút đã đi qua thẳng vào gốc.
- union(a, b) tìm cả hai gốc và, theo hợp theo hạng, gắn cây thấp hơn vào dưới cây cao hơn.
- Hai phần tử được nối với nhau khi và chỉ khi find trả về cùng một đại diện.
Khi nào nên dùng?
- Thuật toán Kruskal tìm Cây khung nhỏ nhất, để phát hiện một cạnh có tạo thành chu trình hay không.
- Truy vấn liên thông động trong đồ thị và mạng khi các cạnh được thêm vào.
- Phát hiện chu trình trong đồ thị vô hướng và các bài toán gom nhóm như phân đoạn ảnh.
Phân tích độ phức tạp
Khi kết hợp cả hợp theo hạng và nén đường, một chuỗi thao tác chạy phân bổ O(α(n)) mỗi thao tác, với α là hàm Ackermann ngược — thực tế là một hằng số nhỏ với mọi n thực tế. Bộ nhớ là O(n) cho mảng cha và mảng hạng.
Câu hỏi thường gặp
Hàm Ackermann ngược α(n) là gì?
Nó tăng chậm đến mức α(n) không quá 4 với mọi kích thước có thể lưu trữ được, nên mỗi thao tác Union-Find được coi là gần như thời gian hằng số.
Vì sao dùng cả hợp theo hạng và nén đường?
Mỗi kỹ thuật riêng lẻ cho O(log n); kết hợp lại giữ cây phẳng và giảm chi phí phân bổ xuống O(α(n)). Hợp theo hạng giới hạn chiều cao cây, còn nén đường rút ngắn các lần tra cứu sau.