# Chữa bài DSU 07/06/2023

Code mẫu các bạn bấm vào chỗ details nhé.

Có một số bạn (không phải một đâu), code DSU bằng struct xong viết constructor kiểu thế này:

vector<int> parent;
DSU(int n): parent(n){}

Xong khởi tạo thế này:

for(int i = 1; i <= n; i++)
    parent[i] = i;

Thế này thì khi $i=n$ nó sẽ access phần tử thứ $n+1$ của `parent` trong khi kích cỡ `parent` là $n$ nên sẽ bị RTE. Có thể trên máy các bạn chạy ok, trong khi trên judge thì bị RTE, vì cái này là [undefined behavior](https://en.wikipedia.org/wiki/Undefined_behavior), tùy môi trường mà kết quả sẽ khác nhau, chẳng ai biết được. Trên lí thuyết thì compiler của các bạn cho phóng tên lửa hạt nhân cũng được.

Tặng các bạn struct DSU uy tín:
:::spoiler

struct DisjointSet{
    vector<int> parent;
    DisjointSet(int n): parent(n + 1){
        for(int i = 1; i <= n; i++) parent[i] = i;
    }

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

    bool join(int u, int v){
        u = find(u);
        v = find(v);
        if(u == v) return false;
        parent[u] = v;
        return true;
    }
};

:::

## Bài 1: [DSU](https://marisaoj.com/problem/130)
- Ứng dụng trực tiếp của DSU, thôi bỏ qua nhé.

## Bài 2: [Tổng thành phần](https://marisaoj.com/problem/131)
- Chỉ cần lưu thêm `sum[i]` là tổng của thành phần liên thông $i$. Khi hợp thành phần $u$ vào thành phần $v$ (`parent[u] = v`) thì thêm tổng của $u$ vào $v$: `sum[v] += sum[u]`.

:::spoiler

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 100005;
 
int n, q, p[MAXN], sz[MAXN], sum[MAXN];
 
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
 
void merge(int x, int y) {
    int px = find(x), py = find(y);
    if (px == py) return;
    if (sz[px] < sz[py]) swap(px, py);
    p[py] = px;
    sz[px] += sz[py];
    sum[px] += sum[py];
}
 
int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        p[i] = i;
        sz[i] = 1;
        sum[i] = i;
    }
    while (q--) {
        int t, u, v;
        cin >> t >> u;
        if (t == 1) {
            cin >> v;
            merge(u, v);
        } else {
            int pu = find(u);
            cout << sum[pu] << '\n';
        }
    }
    return 0;
}

:::

## Bài 3: [Cây khung nhỏ nhất](https://marisaoj.com/problem/134)
- Sử dụng thuật toán Kruskal như đã được trình bày ở [đây](https://vnoi.info/wiki/algo/graph-theory/minimum-spanning-tree.md#c%C3%A1c-thu%E1%BA%ADt-to%C3%A1n-t%C3%ACm-c%C3%A2y-khung-nh%E1%BB%8F-nh%E1%BA%A5t)

## Bài 4: [Xóa cạnh](https://marisaoj.com/problem/134)
- DSU chỉ hỗ trợ thao tác hợp chứ không hỗ trợ thao tác xóa nên mình sẽ xử lý các truy vấn theo thứ tự ngược lại. Đây gọi là xử lí **offline**, nhập hết các truy vấn vào rồi mới xử lí theo thứ tự nào đó cho phù hợp. Ngược lại xử lí **online** là nhập truy vấn đến đâu rồi xử lí đến đấy luôn.

- Xét test mẫu ta có một cái đồ thị như thế này:

- Có các truy vấn lần lượt là
+ Xóa cạnh $4$, hỏi đỉnh $4$.
+ Xóa cạnh $2$, hỏi đỉnh $3$.
+ Xóa cạnh $1$, hỏi đỉnh $1$.

- Khi xóa các cạnh trong truy vấn, các đồ thị sẽ trông như này:

- Bây giờ mình sẽ làm ngược lại, đầu tiên sẽ dựng lại đồ thị cuối cùng, tức là đồ thị sau khi xóa hết cạnh ở cả $q$ truy vấn. Trong trường hợp này là đồ thị sau khi truy vấn 3:

- Mô tả quá trình xử lí các truy vấn theo thứ tự từ cuối lên đầu:

- Dễ thấy các đồ thị này y hệt các đồ thị khi xóa các cạnh lần lượt theo thứ tự, vừa thêm các cạnh vào, vừa trả lời truy vấn.

- Code

:::spoiler

#include <bits/stdc++.h>
using namespace std;
 
#define pi pair<int, int>
#define inf32 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
#define all(x) x.begin(), x.end()
#define Unique(v) v.erase(unique(all(v)), v.end());
#define int long long
#define setinf(d) memset(d, inf32, sizeof d)
#define setneg(d) memset(d, -1, sizeof d)
#define set0(d) memset(d, 0, sizeof d)
#define Log2(x) 63 - __builtin_clzll(x)
#define oo 2e18
#define mod 1000000007
#define FILENAME "f"
 
const int maxn = 2e5 + 5;
 
struct DisjointSet{
    vector<int> parent, sz;
    DisjointSet(int n): parent(n + 1), sz(n + 1){
        for(int i = 1; i <= n; i++) parent[i] = i, sz[i] = 1;
    }
 
    int find(int u){
        if(u != parent[u]) return parent[u] = find(parent[u]);
        return u;
    }
 
    bool join(int u, int v){
        u = find(u);
        v = find(v);
        if(u == v) return false;
        sz[v] += sz[u];
        parent[u] = v;
        return true;
    }
};
 
int n, m, q;
pi edge[maxn], qr[maxn];
int er[maxn];
int ans[maxn];
bool ok[maxn];
 
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
    cin >> n >> m >> q;
    for(int i = 1; i <= m; i++)
        cin >> edge[i].first >> edge[i].second, ok[i] = true;
 
 
    for(int i = 1; i <= q; i++){
        cin >> qr[i].first >> qr[i].second;
        if(ok[qr[i].first]){
            er[i] = qr[i].first;
            ok[qr[i].first] = false;
        }
    }
 
    DisjointSet d(n);
 
    for(int i = 1; i <= m; i++)
        if(ok[i])
            d.join(edge[i].first, edge[i].second);
 
    for(int i = q; i >= 1; i--){
        ans[i] = d.sz[d.find(qr[i].second)];
        if(er[i]) d.join(edge[er[i]].first, edge[er[i]].second);
    }
 
    for(int i = 1; i <= q; i++)
        cout << ans[i] << '\n';
}

:::

## Bài 5: [Đỗ xe](https://marisaoj.com/problem/133)
- Ta sẽ sử dụng DSU để nhóm những chỗ đỗ xe đã có xe thành một nhóm.
- Xét ví dụ có $4$ chỗ đỗ xe, người đỗ xe muốn các chỗ đỗ theo thứ tự $2, 3, 2, 3$.
- Ban đẩu tất cả các chỗ đỗ xe còn trống:
- Tiếp theo người đầu tiên vào và muốn chỗ thứ $2$, do không có ai đã đỗ nên vào luôn:
- Người thứ hai tiếp muốn chỗ thứ $3$, uki luôn, lúc này chỗ thứ $2$ và chỗ thứ $3$ đã thuộc một nhóm trong DSU:
- Người thứ ba muốn chỗ thứ $2$, do đã bị chiếm trước, ta tìm được chỗ thứ $2$ đã thuộc một nhóm kéo dài từ chỗ thứ $2$ đến chỗ thứ $3$, nên ta biết được chỗ trống tiếp theo là chỗ thứ $4$ -> vào chỗ thứ $4$. Cả ba chỗ $2,3,4$ giờ đã thuộc cùng một nhóm.
- Đến người thứ tư muốn vào chỗ thứ $3$, do đã bị chiếm, ta biết chỗ này thuộc một nhóm từ $2$ đến $4$, nên đỗ vào chỗ tiếp theo, chính là quay lại $1$, đã xếp hết các xe:

Thêm một ví dụ cho việc gộp nhóm sau khi đỗ xe:
- Trước, có hai nhóm, một từ $2$ đến $3$, một từ $5$ đến $6$:
- Sau khi có xe đỗ vào vị trí $4$, tạo thành một nhóm lớn từ $2$ đến $6$:

Code
:::spoiler

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5;
int n;
int parent[N],r[N],arr[N],ans[N];
int root(int v)
{
    if(parent[v]!=v)
    return parent[v]=root(parent[v]);
    return v;
}
void Union(int u,int v)
{
    u=root(u);
    v=root(v);
    if(u==v)
    return;
    parent[u]=v;
    if(r[u]==r[v])
    r[v]++;
    return;
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for(int i=0;i<N;i++)
    {
        parent[i]=i;
        r[i]=1;
    }
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>arr[i];
    for(int i=1;i<=n;i++)
    {
        int ra=root(arr[i]);
        ans[i]=ra;
        if(ra==n)
        Union(ra,1);
        else
        Union(ra,ra+1);
    }
    for(int i=1;i<=n;i++)
    cout<<ans[i]<<" ";
    return 0;
}

:::