Trong nhiều trường hợp, ta phải quản lý các đỉnh trong đồ thị theo nhiều thành phần rời nhau. Để giải quyết vấn đề này, DSU là một trong những lựa chọn tối ưu.
Trong cấu trúc DSU, đại lượng đặc trưng cho mỗi nút là nút cha của nó. Hiển nhiên, nếu nút đang xét là nút gốc của tập không giao [disjoint set] chứa nó thì giá trị đó là chính nó.
Có 2 thao tác chính có thể thực hiện trên cấu trúc DSU:
- find[int z]: Tìm nút gốc của tập không giao [disjoint set] chứa nó.
- merge[int a, int b]: Nhập 2 tập hợp có chứa nút a và nút b. Nếu 2 nút nằm ở chung 1 tập hợp thì không cần làm gì cả.
Thông thường, các thao tác này sẽ cần độ phức tạp O[V].
Nếu ở thao tác merge, ta thực hiện merge theo phương pháp nhập tập không giao nhỏ hơn vào tập không giao lớn hơn, thì độ phức tạp sẽ chỉ là O[log[V]].
Để thực hiện được điều này, ta cần xét thêm một đại lượng nữa, đó là kích thước của mỗi tập không giao. Giá trị này sẽ được truy vấn ở nút gốc của mỗi tập.
Tham khảo thêm ví dụ về cách cài đặt [C++] tại đây: Disjoint set union [DSU]
Tham khảo thêm ở bài viết về thuật toán Kruskal.
Bài toán tham khảo: Codeforces 939D – Love Rescue
Tóm tắt đề bài:
Cho 2 xâu cùng có độ dài n [1 x >> y; // doc cap ghep x y
soNhom -= Union[x,y]; // gop nhom co x voi nhom chua y
// giam so nhom neu hai nhom khac nhau
}
f.close[]; // dong input file
// Giai trinh ket qua
cout