# Disjoint Set Union (DSU)

## Giới thiệu:
Disjoint Set Union (DSU) 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.

## Bài toán:
Cho một đồ thị có $n$ đỉnh, ban đầu không có cạnh nào. Có hai loại truy vấn như sau:
* $union~u~v$ - Thêm một cạnh giữa đỉnh $u$ và đỉnh $v$ trong đồ thị.
* $get ~u~v$ - Kiểm tra xem đỉnh $u$ và $v$ có cùng thuộc một thành phần liên thông hay không. Nếu có in ra "YES", ngược lại in "NO" *(không có dấu ngoặc kép)*.

### Ý tưởng:
Ta sẽ giải quyết truy vấn $2$ bằng cách xây dựng hàm $get\_root()$ để tìm ra được gốc ($root$) của đỉnh $u$.
#### Thuật toán ngây thơ:
Giả sử với đồ thị này, ta tìm gốc của đỉnh $u$ bất kì bằng cách nhảy từng bước lên trên cho đến khi nào tìm được thì dừng. Ta dễ dàng thấy được trong trường hợp tệ nhất, độ phức tạp là $O(n)$.
#### Code:

int get_root(int u) {
    if (p[u] == u) return u; // Trả về đỉnh u nếu như đỉnh u là gốc của cây
    int root_u = get_root(p[u]); // Đệ quy lên cha của đỉnh u
    return root_u;
}

### Cải tiến bằng phương pháp nén đường đi
Ta sẽ cải tiến bằng cách sau khi tìm được gốc $u$, ta cập nhật $p[u]$ để trỏ trực tiếp đến gốc đó.


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

Ngoài ra ta có thể viết ngắn gọn như sau:

int get_root(int u) {
    return (p[u] == u ? u : p[u] = get_root(p[u]));
}

Ta tìm gốc của $u$ và $v$. Gọi $ru$ và $rv$ lần lượt là gốc của đỉnh $u$ và $v$.

Từ đó ta xây dựng mảng $sz[]$ để lưu kích thước tập hợp:
* Nếu $sz[ru] > sz[rv]$ thì ta gán $p[rv] = ru$ và $sz[ru] += sz[rv]$. Nghĩa là nối đỉnh $v$ vào đỉnh $u$ và cập nhật lại kích thước của chúng.
* Trường hợp còn lại thì ta gán $p[ru] = p[rv]$ và $sz[rv] += sz[ru]$

Còn đối với truy vấn $2$ thì ta chỉ cần kiểm tra xem gốc của $u$ và $v$ đã giống nhau chưa, nếu giống thì chúng cùng thuộc một thành phần liên thông.

#### Code:

#include <bits/stdc++.h>

using namespace std;

#define maxn 100005

string s;
int n, m, p[maxn], sz[maxn];

int get_root(int u) {
    if (p[u] == u) return u;
    int root_u = get_root(p[u]);
    p[u] = root_u;
    return root_u;
}
int main() {
    cin >> n >> m;
    iota(p + 1, p + n + 1, 1);
    memset(sz, 1, sizeof sz);
    
    while (m--) {
        string s; cin >> s;
        int u, v; cin >> u >> v;
        int ru = get_root(u), rv = get_root(v);
        if (s[0] == 'u') {
            if (sz[ru] > sz[rv]) {
                p[rv] = ru;
                sz[ru] += sz[rv];
            } else {
                p[ru] = rv;
                sz[rv] += sz[ru];
            }
        } else {
            if (ru == rv) cout << "YES" << '\n';
            else cout << "NO" << '\n';
        }
    }
    return 0;
}

Thật ra với code trên ta cũng chẳng cần mảng $size$ nên có thể viết thành:

#include <bits/stdc++.h>
using namespace std;

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define int long long
#define setConstant memset

const int maxn = 100005;

int p[maxn];

int get_root(int u) {
	return (p[u] == u ? u : p[u] = get_root(p[u]));
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, m; cin >> n >> m;
	iota(p + 1, p + n + 1, 1);
	while (m--) {
		string s; cin >> s;
		int u, v; cin >> u >> v;
		int ru = get_root(u), rv = get_root(v);
		if (s[0] == 'u') p[rv] = ru;
		else {
			if (ru == rv) cout << "YES" << '\n';
			else cout << "NO" << '\n';
		}
	}
	return 0;
}

### Bài tập áp dụng:
#### Bài 1: Mocha and Diana (Easy Version)
Nguồn: https://codeforces.com/problemset/problem/1559/D1

Một rừng là một đồ thị vô hướng không chứa chu trình (không nhất thiết phải liên thông).

Mocha và Diana là bạn bè ở Zhijiang, cả hai đều có một rừng với các đỉnh được đánh số từ $1$ đến $n$, và họ muốn thêm các cạnh vào rừng của mình sao cho:
* Sau khi thêm các cạnh, cả hai đồ thị vẫn là các rừng.
* Họ thêm các cạnh giống nhau. Tức là, nếu một cạnh $(u,v)$ được thêm vào rừng của Mocha, thì một cạnh $(u,v)$ cũng được thêm vào rừng của Diana, và ngược lại.

Mocha và Diana muốn biết số lượng cạnh tối đa mà họ có thể thêm và cách thêm cạnh.

**Đầu vào:**
* Dòng đầu tiên gồm ba số $n$, $m_1$, $m_2$ - số lượng đỉnh và số lượng cạnh ban đầu trong rừng của Mocha và Diana.
* $m_1$ dòng tiếp theo chứa hai số nguyên $u$ và $v$ - các cạnh trong rừng của Mocha.
* $m_2$ dòng tiếp theo chứa hai số nguyên $u$ và $v$ - các cạnh trong rừng Diana.

**Đầu ra:**
* Dòng đầu tiên chỉ chứa một số nguyên $h$ - số lượng cạnh tối đa mà Mocha và Diana có thể thêm (trong mỗi rừng).
* $h$ dòng tiếp theo bao gồm hai số nguyên $u$ và $v$ - cạnh thêm vào mỗi lần.

**Lưu ý:** Có thể có nhiều câu trả lời, bạn có thể in ra bất kì câu trả lời nào.

#### Ý tưởng:
Về phần nối hai đỉnh lại với nhau ta sẽ làm như đã được trình bày ở trên.

#### Code:

struct DSU {
	vector<int> p;
	DSU(int n) {
		p.resize(n + 1);
		iota(all(p), 0);
	}
	int get_root(int u) {
		return (p[u] == u ? u : p[u] = get_root(p[u]));
	}
	void merge(int u, int v) {                 
		int ru = get_root(u), rv = get_root(v);
		if (ru == rv) return;
		p[rv] = ru;
	}
};

Ta khởi tạo một mảng để lưu cặp giá trị, sau đó duyệt hết các trường hợp có thể. Ta rút ra được điều kiện sau:

Nếu gốc $i$ của $d1$ khác gốc $j$ của $d1$ và gốc $i$ của $d2$ khác gốc $j$ của $d2$ thì ta lưu cặp giá trị $i$ và $j$ vào mảng kết quả, sau đó nối đỉnh $i$ vào $j$ của $d1$ và $i$ vào $j$ của $d2$.