DSU

Để có thể hiểu vấn đề hơn mình nghĩ các bạn thử giải bài này trước khi vào bài viết. Matrix Electron

Lời mở đầu :

Đây là tài liệu do bản thân mình tự soạn thảo, nội dung bao gồm các kiến thức căn bản, với mục đích giúp các bạn dễ bắt đầu hơn và chia sẻ góc nhìn của mình về một thuật toán, mình muốn nhắn nhủ các bạn có mục đích cao, hãy tự tìm nguồn tài liệu, bài để làm thêm.

Vì đây là bài do mình tự soạn thảo rất có thể có nhiều lỗi, nên nếu ae thấy sai, hay lỗi gì đừng ngần ngại phản hồi cho mình, mình rất cần những phản hồi để giúp bài viết tốt hơn.

Một số quy tắc dùng trong bài viết:

tập = tập hợp = nhóm (các phần tử)

Vấn đề:

Cho n số nguyên ~ a_{1} , a_{2} , ... a_{n} ~ , ban đầu mỗi ~a_i~ ~(1 \le i \le n)~ thuộc một tập riêng biệt.

1. Cho hai số nguyên i và j ~ (1 \le i, j \le n) ~ , kiểm tra xem ~a_i~ và ~a_j~ có cùng một tập hay không.

2. Cho hai số nguyên i và j ~(1 \le i,j \le n)~ , gộp tập có chứa ~a_i~ và tập có chứa ~a_j~ lại với thành một tập.

Tóm tắt, làm gọn vấn đề :

Ta có thể xem là ban đầu có n, tập tập thứ i ban đầu chứa i thay vì chứa ~a_i~ để phân biệt giữa các ~a_i~ có giá trị bằng nhau.

Ta tập trung vào 2 thao tác :

1. Tìm tập của một phần tử, ví dụ ta tìm tập ~a_1~ thì ta sẽ tìm tập chứa 1.
2. Gộp hai tập chứa ~a_i~ và ~a_j~ - ta sẽ gộp hai tập chứa i và j

DSU quản lý các tập, mỗi tập dưới dạng 1 cây.

Tóm tắt nhanh về cây, bạn nào đã có kiến thức về cây có thể bỏ qua phần này !

    Đồ thị nói chung và cây nói riêng bao gồm các đỉnh(node) và các cạnh (edge)

    Trong đó, với cây, cạnh đóng vai trò nối hai đỉnh lại với nhau.

    Mỗi node trong cây có quan hệ cha(parent) - con(child) với các node khác, mỗi node **chỉ có thể có 1 cha** nhưng lại có thể có nhiều con.

    Cũng chính vì mỗi node chỉ có một cha nên, ta có thể lưu đầy đủ thông tin về quan hệ các node của một tree, bằng 1 mảng 1 chiều p, với p[i] lưu chỉ số phần tử cha của phần node i.

    Mỗi cây có duy nhất 1 node không có cha - root, là một node rất đặc biệt nên ta sẽ có 1 cách để đánh dấu chúng, cách sử dụng trong bài viết này là: các root *9 sẽ được đánh dấu bằng cách p[u] = u, hay node chính là cha của node.

*9 : gọi là "các" vì như bạn thấy dsu quản lí nhiều tập (chính là cây), mỗi cây có một root nên trong 1 dsu sẽ tồn tại nhiều root.

    Đầu mũi tên là cha, cuối mũi tên là con, cha của 10 là 8 nên p[10] = 8

Cây là một đồ thị liên thông (tức là tất cả các node liên kết với nhau) với số cạnh ít nhất, cây chứa 5 phần tử chỉ cần đúng chính xác 4 cạnh để liên kết chúng.

Một DSU cơ bản.

Trạng thái ban đầu của DSU:

Ban đầu DSU bao gồm n phần tử (n ở đây ví dụ là 10), mỗi phần tử thuộc một tập riêng biệt, mỗi cây ở đây chỉ bao gồm 1 phần tử cũng chính là root của cây ~p_i~ = i ~(1 \le i \le n)~

Trạng thái của DSU sau khi thực hiện một vài thao tác gộp.

Theo hình trên bạn có thể thấy DSU đang có 4 tập riêng biệt : {1,3,5,6,7}, {8, 10}, {2,9}, {4} mỗi tập là 1 cây.

Vậy làm thế nào để thực hiện 2 thao tác ta muốn dựa vào DSU.

Thao tác 1 : tìm tập của một phẩn tử

Vậy làm thể nào để phân biệt hai phần tử thuộc 2 tập khác nhau, làm thế nào để biết hai phần tử thuộc cùng 1 tập.

Theo cấu trúc cây trên, 2 phần tử cùng một tập sẽ có cùng 1 root, hay các phần tử cùng một cây sẽ có cùng 1 root và ngược lại hai phần tử khác nhau về tập chứa chúng, chắc chắn sẽ có hai root khác nhau.

Và cuối cùng gọi node a là con của node b, vậy root của node b cũng là root của node a, dựa trên đó ta có thể xây dựng hàm đệ quy với điều kiện dừng khi node đang tìm là root, như ta đã nói ở trên ta đặt quy ước là x là root khi và chỉ khi p[x] = x;

Trước khi đến với hàm find ta sẽ có hàm khởi tạo DSU với những nhận xét từ đầu đến giờ.

void initDSU(int n){
    // ban đầu n phần tử là n phần tử riêng biệt
    for(int i = 0 ; i < n ; i++)
        p[i] = i; 
}

int find(int u){
    // điều kiện dừng, khi node ta tìm được là root
    if(u==p[u]){
        return u;
    }
    // nếu không vì root của p[u] == root của u nên ta đệ quy như sau.
    return find(p[u]);
}

Hàm find này chạy đúng như những gì ta cần, nhưng thế này chưa làm nên được sự ưu việt, ta sẽ nhắc lại và cải tiến hàm này ở Cải tiến số 1. Với hàm find trên ta có thể tìm được root của một node bất kì từ đó phân biệt được các node cùng hay khác tập.

Thao tác số 2: Gộp 2 tập.

Nếu các bạn có gặp khó khăn với problem mà mình đề cập tới ở đầu bài, thì thao tác gộp này có lẽ là vấn đề mà bạn gặp.

Với DSU thao tác gộp đơn giản hơn vì để phân biệt 2 tập, ta dựa vào root, vậy để hợp nhất hai tập ta chỉ cần làm cho 2 cây đại diện cho 2 tập có cùng root là được, chi tiết như sau.

Vd: ta muốn gộp 2 tập của phần tử 3 và 10 lại.

Đầu tiên ta cần tìm 3 và 10 thuộcr tập nào bằng hàm find, nếu chúng cùng một tập, thì ta không phải gộp nữa, trong trường hợp này 3 và 10 không thuộc cùng 1 tập

Ta có 1 và 8 lần lượt là tập cũng như root của 3 và 10.

Để gộp hai tập khác nhau ta đơn giản, hiện tại ra đang có 2 root là 1 và 8, ta chọn 1 root làm con của root còn lại, ta chọn 8 làm con của 1 bằng cách gán p[8] = 1,

DSU sau khi gộp

Implementation

void merge(int a,int b){
    int ra = find(a);
    int rb = find(b);
    if(ra!=rb){
        p[rb] = ra;
    }
}

Optimization #1: fast find ( ff :)) )

Chúng ta sẽ nói sâu hơn về thao tác find và làm cho nó trở nên siêu nhanh.

Rõ ràng độ phức tạp, độ nhanh chậm của hàm find phụ thuộc vào độ dài của quãng đường nó đi trong cây để đến được root, ta dễ dàng có thể tìm được 1 trường hợp đơn giản như sau, độ phức tạp là 1e5, vậy ta không thể thực hiện được nhiều truy vấn. Người sinh test hoàn toàn có thể để 1 test duy nhất là bắt chúng ta phải find(100000) nhiều lần, việc này có thể giải quyết được bằng nhận xét sau.

Nhưng ta có một số nhật xét rõ ràng là

• Tất cả các node mà hàm find duyệt qua trên đường đi đến root đều có chung 1 root chính là root mà chúng ta đang tìm

  • theo ví dụ trên thì tất cả các node 1 đến 1e5 đều có chung 1 root là 1.

• Việc cứ tìm đi tìm lại root của node 1e5 trên cùng con đường dài ngoằn đó là lãng phí, sau khi tìm được root của 1e5 là 1 ta hoàn toàn có thể gán p[1e5] = 1 để rút ngắn cho các lần find(1e5) sau chỉ còn là O(1)

  

Và hơn thế nữa tất cả các nút trên đường đi (2, 3, 4, .., 99998, 99999) đều có root là 1, ta cũng có thể làm điều tương tự với tất cả các node này.

Vậy là chỉ với 1 lần find(1e5) ta đã rút ngắn đường đi cho rất nhiều find(x) chỉ còn lại O(1), bạn nên chú ý ta làm được điều này vì ta đang làm việc với tập, chỉ quan tâm tới root của một node là gì.

Sau đây là implement của hàm find;

int find(int u){
    if(p[u]==u) return u;
    return p[u] = find(p[u]);
}

Optimization 2 : merging

Ở phần trước mình có cài đặt như sau :

void merge(int a,int b){
    int ra = find(a);
    int rb = find(b);
    if(ra!=rb){
        p[rb] = ra;
    }
}

Hẳn các bạn cũng đã đặt câu hỏi tại sao lại luôn gán cha của rb là ra, hay trong khi gộp 2 tập của 2 node a và b ta lại chọn ra làm root của tập sau khi gộp (tập kết quả) mà không phải rb. Đúng vậy việc chọn như vậy rất tệ, có rất nhiều cách để chọn 1 trong 2 root ra hoặc rb để làm root của tập sau khi gộp random cũng là một cách ( mình k hề đùa trang cp-algo có đề cập), nhưng không hiệu quả bằng các cách khác.

Khi chọn 1 làm root của tập kết quả sau khi gộp

Khi chọn 8 làm root của tập kết quả sau khi gộp

Mình thường sử dụng thêm một mảng để quyết định việc này - mảng sz với sz[i] là số lượng phần tử của cây có root là i. Logic của mảng này theo mình hiểu như sau, bạn để ý: khi chọn ra làm root của tập kết quả thì tất cả các phần tử của cây có root rb sau khi gộp, khi dùng hàm find() thì quãng đường cần đi sẽ tăng thêm một đơn vị so với trước khi gộp.

Vd theo hai hình minh họa ở ngay trên, bạn chọn 1 là root của tập kết quả thì phần tử 10 thuộc cây có root 8 trước khi gộp chỉ cần thực hiện đúng 1 lần đệ quy để đến được root của nó là 8, sau khi gộp nó cần đi thêm 1 đoạn từ 8->1 nữa, điều này xảy ra với tất cả các phần tử của cây có root là rb. Và đương nhiên các phần tử của cây có root ra không hề thay đổi gì.

Và ngược lại khi chọn rb làm root của tập kết quả, mỗi phần tử của cây có root là ra khi chạy hàm find() sẽ phải đi thêm 1 đơn vị sau khi gộp.

Vậy ta có thể suy ra độ tăng lên của độ phức tạp khi gộp 2 tập có liên quan đến việc chọn root của tập kết quả. Khi chọn ra làm root của tập kết quả chương trình có thể tăng lên một độ phức tạp tương ứng với sz[rb] và ngược lại chọn rb làm root của tập kết quả độ phức tạp chương trình có thể tăng lên một lượng tương đương với sz[rb]. Vậy để độ phức tạp tăng ít nhất ta sẽ chọn root có sz[root] là lớn nhất.

Ta sửa lại hàm khởi tạo và merge như sau

void initDSU(int n){
    // ban đầu n phần tử là n phần tử riêng biệt, do đó sz[i] = 1
    for(int i = 0 ; i < n ; i++)
        p[u] = i, sz[i] = 1; 
}

void merge(int a,int b){
    int ra = find(a);
    int rb = find(b);
    if(ra!=rb){
        // đảm bảo rằng sz[ra] >= sz[rb];
        if(sz[ra] < sz[rb]) swap(ra);
        p[rb] = ra;
        sz[ra]+=sz[rb];
    }
}

Ngoài ra còn khá nhiều cách để có thể lựa chọn root của tập kết quả, vd như kết hợp mảng sz và rank được đề cập đến trong trang cp-algo .

DSU là một cấu trúc dữ liệu ngắn ngọn, đơn giản, giải quyết được một vấn đề mà đọc đề thì rất đơn giản, nhưng để tìm được cách triển khai tốt thì hơi mệt, bạn nào đã thử giải vấn đề ở đầu bài có lẽ sẽ hiểu.