Data structure Disjoint Set Union or DSU

 

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

https://en.wikipedia.org/wiki/Disjoint-set_data_structure#:~:text=In%20computer%20science%2C%20a%20disjoint,a%20set%20into%20disjoint%20subsets.

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;

}

>>>>>>> to be continue

3. Bài tập:

    Bài 1: QBMST

    Bài 2: BuildCity

    Bài 3: IOBIN

-