{%hackmd @themes/dracula %}
<style>
.markdown-body pre {background-color: #1E1E1E;border: 1px solid #555 !important;color: #73BCE0;border-radius:8px;/*border-radius:0px;*/ } .markdown-body pre .htmlembedded {color: #C8D4C8 !important; } .markdown-body pre .hljs-tag {color: #6D726E; } .markdown-body pre .token.keyword {color: #C586C0; } .markdown-body pre .token.string, .markdown-body pre .hljs-string {color: #C68362; } .markdown-body pre .hljs-comment, .markdown-body pre .token.comment {color: #6A9955; } .markdown-body pre .hljs-attr {color: #73BCE0; } .markdown-body pre .hljs-name {color:#569CD6; } .markdown-body pre .token.operator {color:#C8D4C8;background:transparent; } .markdown-body pre .token.property {color: #73BCE0; } .markdown-body pre .token.function {color: #DCDCAA; } .markdown-body pre .token.builtin {color: #34B294; } .markdown-body pre .token.number {color: #B5CEA8; } .markdown-body pre .token.constant {color: #3BC1FF; } .markdown-body pre .hljs-addition {color: #96D47D;background: #373D29; } .markdown-body pre .hljs-deletion {color: #E76A6A;background: #4B1818; } .markdown-body pre .hljs-selector-class {color: #D7BA5F; } .markdown-body pre .hljs-attribute {color: #9CDCFE; } .markdown-body pre .hljs-number {color: #C68362; } .markdown-body pre .hljs-meta {color: #2C7CD6; }
</style>
# Disjoint Set Union
*Hay còn gọi là* **DSU**..

⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⡄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⣠⡄⡀⠀⠀⠀⠀⠀⠀⠀⠀⣯⣜⡐⢢⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⢘⣷⣼⢶⡀⠀⠀⠀⠀⠀⠀⠀⣽⣿⣾⣐⣇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠼⠛⡛⣾⣤⣀⠀⠀⠀⠀⠀⢀⣿⣿⢿⠿⠗⠤⠤⢄⡀⠀⠀⠀⠀⠀⠀
⣮⣦⣯⣽⣿⣷⣿⣵⢢⢤⣤⡖⠉⢈⡤⠆⠀⢀⡀⠈⠁⠒⠚⡴⡀⡀⠀⠀
⠙⠿⠿⠛⠈⠹⣿⢯⡟⡳⣨⠞⠀⠀⣄⣤⣶⢖⠒⠲⣤⣢⣾⣿⡿⢨⠄⠀ (Depchoai - Sitina - Union)
⠀⠀⠀⠀⠀⠀⠘⣏⣿⡇⢘⡢⢰⣿⣿⣿⣿⣧⣶⣶⣿⣿⣿⣿⣿⣄⢧⣂
⠀⠀⠀⠀⠀⠀⠀⠈⢺⠿⡴⢧⠿⣿⣿⣿⣿⠿⢿⣿⣿⣿⣿⣿⣿⣿⡮⣷
⠀⠀⠀⠀⠀⠀⡰⣱⣴⣯⣴⣎⣾⢷⣿⣿⣿⣆⠣⢞⠛⡯⣙⠳⢻⡝⠷⢿
⠀⠀⠀⠀⠀⠀⠱⢿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠯⢷⣎⣵⣒⡬⠌⠥⠒⠈⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠉⠉⠉⠋⠉⠉⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀

++*Member*++
1. Đặng Thành Nghĩa :coffee:
2. Thân Đức Minh Duy :popcorn:
3. Nguyễn Đăng An :lollipop:

### Layout
* [Giới thiệu](#Giới-thiệu)
* [Lịch sử](#Lịch-sử)
* [Bài toán 1](#Bài-toán-1)
* [Hướng dẫn](#Hướng-dẫn)
* [DSU cơ bản](#Lấy-lại-gốc-sad_nghiaaa_noise)
* [Bài toán 2](#Bài-toán-2)
* [Hướng dẫn](#Hướng-dẫn1)
* [Bài toán 3](#Bài-toán-3)
* [Hướng dẫn](#Hướng-dẫn2)
* [Bài toán 4](#Bài-toán-4)
* [Hướng dẫn](#Hướng-dẫn3)
* [Bài toán 5](#Bài-toán-5)
* [Hướng dẫn](#Hướng-dẫn4)
* [Code D:](#Mã-giả)
## Giới thiệu

* **Disjoint Set Union** hay **DSU**, là một cấu trúc dữ liệu hữu dụng và thường xuyên được sử dụng trong các kì thi CP. **DSU**, đúng như tên gọi của nó, là một *cấu trúc dữ liệu* có thể quản lí một cách hiệu quả một tập hợp của các tập hợp.
* Ý tưởng của thuật toán là ta sẽ đặt phần tử đại diện cho mỗi tập hợp (hay còn gọi là ***root***), và lưu các thông tin cần thiết tại phần tử đó. Với mỗi lần gộp 2 tập thành 1, ta sẽ sử dụng thông tin thể hiện trên ***root*** của cả 2 tập.
## Lịch sử
* **Rừng các tập rời nhau** lần đầu tiên được nhắc đến vào năm 1964, bởi 2 nhà khoa học *Bernald A. Galler* và *Michael J. Fischer*.
* Năm 1973, *Hopcroft* và *Ullman* cho rằng độ phức tạp để hợp các tập là gần với ***O*(log(*N*))**
* Năm 1975, *Tarjan* chứng minh được thuật toán này có độ phức tạp <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>O</mi><mo stretchy="false">(</mo><mi>&#x3B1;</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo></math> - là nghịch đảo của **hàm số Ackermann**. Đồ thị của hàm số này có bước tiến *rất chậm* theo n.
* Theo dòng thời gian, một số *biến thể* của CTDL này đã được phát triển, với hiệu suất ++tốt hơn++ trong một số dạng bài nhất định. *Gabow* và *Tarjan* cho thấy nếu các tập hợp được quản lí chặt chẽ, độ phức tạp **tuyến tính** sẽ thật sự xuất hiện 🤯🤯.

## Bài toán 1

Cho đồ thị gồm N đỉnh và không có cạnh nối. Có Q truy vấn với nội dung:
• Thêm cạnh nối giữa 2 đỉnh U và V.
• Hỏi 2 đỉnh U và V có chung một thành phần liên thông không ?
### Hướng dẫn
* Ta sẽ coi mỗi thành phần liên thông là một *tập hợp* gồm các phần tử là các đỉnh có cạnh nối với nhau.
* Như vậy, ta sẽ tập trung vào cấu trúc dữ liệu DSU để giải quyết bài toán.
### Lấy lại gốc ~~*:sad_nghiaaa_noise:*~~

* Để giải quyết bài toán này, ta sẽ xây dựng một cấu trúc dữ liệu có hai thao tác như sau:

1. **Union_sets(a, b)** - gộp tập hợp chứa phần tử *a* và tập hợp chứa phần tử *b* thành một.
2. **Find_set(v)** - cho biết đại diện của tập hợp có chứa phần tử *v*.

• Ta có thể xử lí các thao tác một cách hiệu quả này với các tập hợp
được biểu diễn dưới dạng các cây, mỗi phần tử là một đỉnh và mỗi cây tương
ứng với một tập hợp.
• Gốc của mỗi cây sẽ là đại diện của tập hợp đó.


Trong đó:
1. Sau truy vấn đầu tiên, tập [1, 2] có *root* = 1, tập [3, 4] có *root* = 3
2. Sau truy vấn thứ hai, tập [1, 2, 3, 4] có *root* = 1
* **Find_set(u)**
1. Cách làm ngây thơ

            int Find_set(int u)
            {
                if (u == dsu[u].root) return u;
                return Find_set(dsu[u].root);
            }

Dễ thấy nếu cây có dạng một đường thẳng, độ phức tạp sẽ lên đến O(n) !

2. Lưu lại gốc của cây

            int Find_set(int u)
            {
                if (u == dsu[u].root) return u;
                dsu[u].root = Find_set(dsu[u].root);
                return dsu[u].root;
            }

Ta thừa biết rằng Find_set(u) là gốc của đỉnh u, vậy sau khi tìm được *root* ta gán nó vào *parent[u]* để rút ngắn khoảng cách.
:keycap_star: Đây là code được cp-er ưa dùng do tính ngắn gọn của nó:

            int Find_set(u){
                return u == dsu[u].root ? u : dsu[u].root = Find_set(dsu[u].root);
            }

* **Union_sets**
1. Cách làm ngây thơ

            void Union_sets(int u,int v)
            {
                u = Find_set(u);
                v = Find_set(v);
                if (u == v) return ;
                dsu[u].root = v;
            }

Nếu áp dụng với optimize **Find_set(u)** ở trên thì ĐPT là *O*(log(*n*))
2. Gộp theo kích thước

            void Union_sets(int u, int v)
            {
                u = Find_set(u);
                v = Find_set(v);
                if (u == v) return ;
                
                // ta chọn u làm root có nhiều thành viên hơn
                if (dsu[u].Size < dsu[v].Size) swap(u,v); 
            
                dsu[u].Size += dsu[v].Size;
                dsu[v].root = u;
            }

Áp dụng với optimize **Find_set(u)** ở trên thì ĐPT là <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>O</mi><mo stretchy="false">(</mo><mi>&#x3B1;</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo></math>

## Bài toán 2
Cho một cây N đỉnh có gốc tại đỉnh 1.
Theo đó là Q truy vấn, tìm đỉnh có chỉ số lớn nhất trong cây con gốc U
nhưng không lớn hơn T.
*Ảnh tham khảo*

### Hướng dẫn
Để thuận tiện, ta sẽ duy trì một set chứa toàn bộ chỉ số thành viên của cây con gốc *U*. Thuật toán **DSU** khá hiệu quả với cách làm thế này.

Nếu ta áp dụng trick *gộp theo kích thước* (nghĩa là chuyển mọi phần tử từ tập *kích thước bé* sang tập *kích thước lớn*) , độ phức tạp khi **Union_sets** tất cả N phần tử chỉ tốn *O*(NlogN) - đủ để giải quyết bài toán với số lượng lớn phần tử!

***Phần Chứng minh***
:::spoiler
• Với điều kiện để chuyển từ tập *A* sang tập *B* là n(*A*) <= n(*B*). Nên sau khi bị chuyển đi, tập A lúc này có số lượng phần tử bé nhất so với lúc chưa chuyển là gấp *2* lần. Vậy sau *x* lần chuyển đi, tập A có kích thước bé nhất là *2^x*
• Do đó, ta dễ thấy rằng mỗi phần tử bị di chuyển sang *tập khác* không quá **logN** lần.
:::
*Hàm Union_sets*

    Void Union_sets(int u, int v)
    {
        u = Find_set(u);
        v = Find_set(v);
        if (u == v) return ;
        
        //chọn tập có kích thước bé hơn cho v
        if (dsu[v].Size > dsu[u].Size) swap(u,v);
        
        //chuyển thông tin từ tập v sang tập u
        dsu[u].List.insert(dsu[v].List.begin(), dsu[v].List.end());
        dsu[v].List.clear();
        
        dsu[u].Size += dsu[v].Size;
        dsu[v].root = u;
    }

## Bài toán 3
Cho đồ thị có N đỉnh và Q truy vấn.
In ra N số là trung vị của mỗi cây con (dựa trên tập index).
### Minh họa

Một ví dụ khác

### Hướng dẫn
Bài này có thể giải hoàn toàn bằng *Euler tour* + *Persistent segment tree* nhưng mà vì code dài ~~và cái tiêu đề + chủ tus ko thik~~ **:D** nên ta sẽ tạm thời bỏ qua
Mặt khác, code đủ nhiều, bạn sẽ nhận thấy cây tree tà đạo này có khả năng ao chình cực mạnh:

Đây là một cây có khả năng tìm được giá trị ở index i (theo mảng đã được *sort*) với DPT *O*(log(*n*)) !! 🤯🤯

Nhưng mà trí nhớ hạn hẹp + áp lực phòng thi thì ai lại nhớ được đống này 💀💀💀

Thế nên ta sẽ tập trung vào 1 trick lỏ đã được thầy V dạy năm ngoái 😈

*Ý tưởng*

* Ta sẽ tách các thành viên trong mỗi tập bằng 2 cây *Max Heap* và *Min Heap* với tính chất:
* Toàn bộ đỉnh trong cây *Max Heap* đều bé hơn cây *Min Heap*
* 2 cây này có số lượng phần tử bằng nhau, nếu tổng thành viên là lẻ thì cho tập *Max Heap* lớn hơn 1 đơn vị.

Khi đó, trung vị của cây tương ứng với *root* cây *Max Heap*


Lí do ta sử dụng 2 cây *Heap* này vì chúng dễ dàng trao đổi thông tin cho nhau, đồng thời thêm nhiều phần tử khác vào mà vẫn duy trì tính chất trên.

*Hàm Union_sets*

    Void Union_sets(int u, int v)
    {
        u = Find_set(u);
        v = Find_set(v);
        if (u == v) return ;
        if (dsu[v].Size > dsu[u].Size) swap(u,v);
        
        //chuyển tập các thành viên sang 1 vector cho dễ tính
        vector<int> listV (begin(dsu[v].Max_H), end(dsu[v].Max_H));
        listV.insert (end(listV), begin(dsu[v].Min_H), end(dsu[v].Min_H));
        
        // duy trì tính chất 1
        for (int p: listV)
        {
            if (p < dsu[u].Max_H)
                dsu[u].Max_H.push(p);
            else dsu[u].Min_H.push(p);
        }
        
        // duy trì tính chất 2
        while(dsu[u].Max_H.size() > dsu[u].Min_H.size() + 1)
        {
            dsu[u].Min_H.push(dsu[u].Max_H.top());
            dsu[u].Max_H.pop();
        }
        while(dsu[u].Max_H.size() < dsu[u].Min_H.size())
        {
            dsu[u].Max_H.push(dsu[u].Min_H.top());
            dsu[u].Min_H.pop();
        }
        
        ...
    }

## Bài toán 4
Cho 1 mảng có N phần tử đánh số từ 1 đến N.
Với mỗi truy vấn cần in ra phần tử có giá trị bé nhất trong đoạn từ [L,R]
Q <= 10^5
N <= 10^7 :))))
### Hướng dẫn
Nếu N <= 10^5 bài này có 500 tỷ cách để làm **D:** , và *DSU* cũng là 1 phương pháp giải có mặt trong 500 tỷ cách đó **:))**

Ý tưởng: Nếu mọi truy vấn đều có dạng **[L,N]**, ta có thể quy ước cho đỉnh *i* có cạnh nối tới đỉnh *j* ++khi và chỉ khi++ ***i* < *j***, với *j* là vị trí *đầu tiên* từ phải sang có *a[i] > a[j]* (*monostack*). Lúc này min(**[L,N]**) chính là *root* của đỉnh *L*.

Tổng quát, xét các truy vấn **[L,R]** được sắp xếp theo *R* tăng dần, khi chuyển đổi *R* ta thêm cạnh nối giữa *R* với các chỉ số *i* chọn *R* làm cạnh nối.

**Độ phức tạp**: *O*(*Q* * log(*Q*) + *N* * α(*N*)))

~~chinh toy cx ko bik noi j :DD~~
### Mã giả

    void compute()
    {
        ... pre monostack ...
        for(int R = 1; R <= N; ++R)
        {
            //xét mọi đỉnh i có cạnh nối tới R để union
            for (int i : edge[R]) 
                Union_sets(i, R);
            
            //kết quả chính là root của L
            for (yo query: List_query[R])
                ans[query.ID] = a[Find_set(query.L)]; 
        }
    }

## Bài toán 5

Cho đồ thị có N đỉnh và Q truy vấn, ban đầu chưa có cạnh nối. Truy vấn có 3 loại:
• Loại 1: Thêm cạnh nối giữa u và v
• Loại 2: Xóa cạnh nối giữa u và v
• Loại 3: Xác định xem u và v có chung thành phần liên thông hay không.
VD:
4 6
1 1 2
1 1 3
1 3 4
3 2 4
2 1 3
3 2 4
*Ảnh minh họa*


### Hướng dẫn
Do có thể xử lí offline, ta sẽ sử dụng thuật **DSU roll back** - một phiên bản nâng cao từ việc kết hợp **DSU** với *interval tree*
Xét mỗi cạnh nối *u-v* được hoạt động trong thời gian từ **[L, R]** (Với **L** là thời điểm *thêm* cạnh, **R** là thời điểm *xóa* cạnh này hoặc là lúc *kết thúc truy vấn* ) và đánh dấu nó trong *cây IT trạng thái*, khi cần truy vấn tại thời điểm *Ti*, ta có thể dựa vào *cây IT* này để biết những cạnh nào đang hoạt động.

### Mã giả
*Thêm cạnh u-v vào segment (hoạt động trên đoạn [L,R])*

    void add_edge(int node, int l, int r, edge & e)
    {
        if (l >= e.L && r <= e.R)
        {
            // thêm cạnh vào đoạn [l,r]
            List_edge[node].push_back(e);
            return ;
        }
        int mid = l + r >> 1;
        if (!(e.L > mid || e.R < l)) add_edge(node << 1, l , mid , e);
        if (!(e.L > r   || e.R < mid + 1)) add_edge(node << 1 | 1, mid + 1 , r , e);
    }

*Walk on tree*

    void dsu_roll_back(int node, int l, int r)
    {
        .. Add every edge in range[l,r] ( push to the stack ) ..
        if ( l == r )
            .. Do some query ..
        else {
            int mid = l + r >> 1;
            dsu_roll_back(node << 1 , l , mid );
            dsu_roll_back(node << 1 | 1 , mid + 1 , r);
        }

        .. Undo changes                  ( pop the stack )    ..
    }