Data structure Disjoint Set Union or DSU
1. Tài liệu tham khảo:
https://vnoi.info/wiki/algo/data-structures/disjoint-set.md
https://cp-algorithms.com/data_structures/disjoint_set_union.html
2. Nội dung:
Cấu trúc dữ
liệu này cung cấp các khả năng sau. Cung cấp một số phần tử, mỗi phần tử
là một tập hợp riêng biệt. Một DSU sẽ có một phép toán để kết hợp hai tập
hợp bất kỳ và nó sẽ có thể cho biết tập hợp nào là một phần tử cụ
thể. Phiên bản cổ điển cũng giới thiệu một hoạt động thứ ba, nó có thể tạo
một tập hợp từ một phần tử mới.
Do đó, giao diện cơ bản của cấu trúc dữ liệu
này chỉ bao gồm ba hoạt động:
· make_set(v) - tạo một tập hợp mới bao gồm
phần tử mớiv
· union_sets(a, b)- hợp nhất hai tập hợp đã chỉ
định (tập hợp chứa phần tử a và tập hợp chứa phần tử b)
· find_set(v) - trả về đại diện của tập hợp
có chứa phần tử v. Đại diện này là một phần tử của tập hợp tương ứng
của nó. Nó được chọn trong mỗi tập hợp bởi chính cấu trúc dữ liệu (và có
thể thay đổi theo thời gian, cụ thể là sau union_sets các lời
gọi). Đại diện này có thể được sử dụng để kiểm tra xem hai phần tử có phải
là một phần của cùng một tập hợp hay không. a và b chính xác trong
cùng một tập hợp, nếu find_set(a) == find_set(b). Nếu
không thì chúng ở các bộ khác nhau.
Cũng trong
một trong các phần phụ, một cấu trúc thay thế của DSU được giải thích, cấu trúc
này đạt được độ phức tạp trung bình chậm hơn O(log n), nhưng có thể mạnh hơn
cấu trúc DSU thông thường.
Xây dựng
cấu trúc dữ liệu hiệu quả
Chúng ta sẽ
lưu trữ các bộ ở dạng cây : mỗi
cây sẽ tương ứng với một bộ. Và rễ cây sẽ là đại diện / lãnh đạo của tập
hợp.
Trong hình ảnh sau đây, bạn
có thể thấy đại diện của những cây như vậy.
Ban đầu,
mọi phần tử bắt đầu như một tập hợp duy nhất, do đó mỗi đỉnh là cây của chính
nó. Sau đó ta kết hợp tập hợp chứa phần tử 1 và tập hợp chứa phần tử 2.
Sau đó ta kết hợp tập hợp chứa phần tử 3 và tập hợp chứa phần tử 4. Và ở bước
cuối cùng, ta kết hợp tập hợp chứa phần tử 1 và tập hợp chứa phần tử 3.
Để thực
hiện, điều này có nghĩa là chúng ta sẽ phải duy trì một mảng parent tham
chiếu đến tổ tiên trực tiếp của nó trong cây.
bool cmp(const edge &a, const edge &b){
return a.w<b.w; //dieu kien sap xep
}
int find(int u){ //Tim to tien
if (cha[u]!=u) cha[u]=find(cha[u]);
return cha[u];
}
bool join(int u, int v){//hop nhat 2 cau chua u, v
u=find(u); v=find(v);//tra ve false neu khong the hop nhat
if (u==v) return false;
if (hang[u]==hang[v]) hang[u]++;
if (hang[u]<hang[v]) cha[u]=v;
else cha[v]=u;
return true;
}
3. Bài tập:
Bài 1: QBMST
Bài 2: BuildCity
Bài 3: IOBIN
-
No comments