Cấu trúc Disjoint Set Union (DSU), hay còn gọi là Union-Find, được dùng để quản lý các tập hợp rời rạc và hỗ trợ hai thao tác chính: kiểm tra xem hai phần tử có cùng tập hợp hay không (Find), và gộp hai tập hợp lại với nhau (Union).

Thay vì lưu trữ toàn bộ cấu trúc cây, DSU chỉ cần mảng parent để lưu cha trực tiếp của mỗi nút. Để kiểm tra tính liên thông giữa hai nút u và v, ta lần theo chuỗi cha đến gốc và so sánh hai gốc này.

Cài đặt cơ bản

int find_root(int x) {
    if (parent[x] == x) return x;
    return find_root(parent[x]);
}

void unite(int a, int b) {
    int root_a = find_root(a);
    int root_b = find_root(b);
    if (root_a != root_b)
        parent[root_b] = root_a;
}

Độ phức tạp trong trường hợp xấu nhất (cây suy biến thành chuỗi) là O(n) cho mỗi thao tác find_root, dẫn đến tổng độ phức tạp O(nm) cho m thao tác — quá chậm cho các bài toán thực tế.

Tối ưu hóa

1. Nén đường đi (Path Compression)

Khi tìm gốc, đồng thời cập nhật cha trực tiếp của mọi nút trên đường đi thành gốc. Điều này làm phẳng cây và tăng tốc các truy vấn sau này.

int find_root(int x) {
    if (parent[x] != x)
        parent[x] = find_root(parent[x]);
    return parent[x];
}

Với tối ưu này, độ phức tạp trung bình mỗi thao tác giảm xuống gần O(log n).

2. Hợp theo kích thước hoặc chiều cao (Union by Size/Rank)

Khi gộp hai cây, luôn gắn cây nhỏ hơn vào gốc của cây lớn hơn để giữ độ cao cây thấp nhất có thể.

void unite(int a, int b) {
    a = find_root(a);
    b = find_root(b);
    if (a == b) return;
    if (size[a] < size[b]) swap(a, b);
    parent[b] = a;
    size[a] += size[b];
}

Kết hợp cả hai kỹ thuật, độ phức tạp trung bình mỗi thao tác là O(α(n)), với α là hàm Ackermann ngược — gần như hằng số (≤ 4 với mọi giá trị n thực tế).

Một số dạng bài tiêu biểu

Bài toán bạn bè

Sử dụng hai DSU riêng biệt để mô phỏng mạng lưới bạn bè trong hai công ty. Kết quả là số người ít hơn trong hai nhóm chứa hai người cho trước.

Bài toán cứu hộ

Dùng kỹ thuật chia nhị phân trên giá trị "đông đúc" lớn nhất. Với mỗi giá trị thử, xây dựng DSU chỉ gồm các cạnh có mức đông đúc ≤ ngưỡng hiện tại, rồi kiểm tra tính liên thông giữa điểm xuất phát và đích.

Đóng trang trại (Closing the Farm)

Xử lý ngược: ban đầu tất cả trang trại đều đóng, sau đó mở dần theo thứ tự ngược lại. Sau mỗi bước, thêm các cạnh nối hai trang trại đang mở và kiểm tra xem toàn bộ đồ thị có liên thông không.

Bài toán phô mai

Biểu diễn các lỗ trong khối phô mai như các nút. Thêm hai nút ảo: đáy (n+1) và đỉnh (n+2). Liên kết lỗ chạm đáy/đỉnh với nút ảo tương ứng. Hai lỗ được nối nếu khoảng cách tâm ≤ 2r. Cuối cùng kiểm tra xem hai nút ảo có cùng tập hợp không.

Phân loại tội phạm (Prisoners)

Sử dụng DSU mở rộng (Extended DSU). Với mỗi tội phạm u, tạo hai bản sao: u (ở nhà tù A) và u + n (ở nhà tù B). Khi xử lý xung đột giữa u và v, nối u với v + n và u + n với v. Nếu tại bước nào đó u và u + n thuộc cùng tập hợp → mâu thuẫn → dừng và trả về ảnh hưởng tại bước đó.

Chuỗi thức ăn (Food Chain)

Mở rộng DSU thành ba miền: u (loài X), u + n (bị X ăn), u + 2n (ăn X). Khi nhận mệnh đề "X ăn Y", kiểm tra tính nhất quán với các quan hệ đã biết. Nếu không mâu thuẫn, cập nhật các mối quan hệ tương ứng bằng cách nối các miền phù hợp.