Disjoint Set Union

Rừng đại diện

Mỗi nhóm là một cây có gốc: mỗi phần tử $u$ trỏ tới một phần tử cha par[u] trong cùng nhóm, riêng gốc trỏ vào chính nó, par[u] = u. Gốc là đại diện của nhóm: hai đỉnh cùng nhóm khi và chỉ khi lần theo par tới cùng một gốc. Gộp hai nhóm chỉ cần nối một gốc vào gốc kia. DSU không nhớ cạnh nào của đồ thị, chỉ nhớ đỉnh nào cùng nhóm với đỉnh nào.

Nối gốc tùy tiện có thể tạo ra một dây dài, mỗi lần tìm gốc tốn $O(n)$. Hai cải tiến xử lý chuyện này:

• Nén đường đi: sau khi tìm được gốc của $u$, cho mọi đỉnh trên đường đi trỏ thẳng vào gốc. Lần sau chúng chỉ cần một bước.
• Gộp theo kích thước: giữ sz[r] là số đỉnh của nhóm có gốc $r$, luôn nối gốc nhóm nhỏ vào gốc nhóm lớn. Mỗi lần một đỉnh bị đẩy sâu thêm một tầng, nhóm của nó ít nhất gấp đôi, nên độ sâu không quá $\log_2 n$.

Có cả hai cải tiến, mỗi thao tác tốn $O(\alpha(n))$ trung bình, với $\alpha$ là hàm ngược Ackermann, không quá 4 với mọi $n$ gặp trong thực tế (chứng minh nằm trong bài của Tarjan, 1975). Chỉ một trong hai cũng đã cho $O(\log n)$ trung bình, đủ cho gần như mọi bài.

Thử với một dây dài 20 nghìn đỉnh:

Không cải tiến nào chậm gấp hàng nghìn lần, còn có một trong hai là đã nhanh. Cứ viết cả hai, vì chỉ tốn thêm một dòng.

ll find(ll u) {
    return par[u] == u ? u : par[u] = find(par[u]);
}

bool unite(ll u, ll v) {
    u = find(u);
    v = find(v);
    if (u == v) return 0;
    if (sz[u] < sz[v]) swap(u, v);
    par[v] = u;
    sz[u] += sz[v];
    return 1;
}

unite trả về việc có thật sự gộp hay không. Hai đỉnh đã cùng nhóm thì số nhóm và kích thước không đổi; quên kiểm tra này là cộng sz hai lần.

Ví dụMạng Đường Đang Mở Rộng

Đề. $n \le 10^5$ đỉnh, $m \le 2 \cdot 10^5$ cạnh được thêm lần lượt. Sau mỗi cạnh in số thành phần liên thông và kích thước thành phần lớn nhất.

Lời giải. Bắt đầu với $n$ nhóm và nhóm lớn nhất kích thước 1. Mỗi lần thêm cạnh nối hai nhóm khác nhau, số nhóm giảm 1 và nhóm mới có kích thước bằng tổng hai nhóm. Kích thước nhóm chỉ tăng, nên nhóm lớn nhất chỉ cần cập nhật bằng max với nhóm vừa gộp, không cần cấu trúc gì thêm. Với ví dụ, cạnh $2\text{-}3$ nối hai cặp thành nhóm 4 đỉnh, cạnh $1\text{-}4$ nằm trong nhóm đó nên không đổi gì.

Bước 1: tìm gốc và gộp. find nén đường đi bằng đệ quy: mỗi đỉnh trên đường trỏ thẳng vào gốc. unite hợp theo kích thước (gốc nhỏ treo vào gốc lớn) và trả về có thật sự gộp hay không.

ll find(ll u) {
    return par[u] == u ? u : par[u] = find(par[u]);
}

bool unite(ll u, ll v) {
    u = find(u);
    v = find(v);
    if (u == v) return 0;
    if (sz[u] < sz[v]) swap(u, v);
    par[v] = u;
    sz[u] += sz[v];
    return 1;
}

Bước 2: sau mỗi cạnh. Chỉ khi thật sự gộp, số nhóm giảm và kích thước lớn nhất có thể đổi.

if (unite(u, v)) {
    comps--;
    best = max(best, sz[find(u)]);
}
cout << comps << ' ' << best << '\n';

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

const ll N = 1e5 + 5;
ll n, m, par[N], sz[N];

ll find(ll u) {
    return par[u] == u ? u : par[u] = find(par[u]);
}

bool unite(ll u, ll v) {
    u = find(u);
    v = find(v);
    if (u == v) return 0;
    if (sz[u] < sz[v]) swap(u, v);
    par[v] = u;
    sz[u] += sz[v];
    return 1;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= n; i++) par[i] = i, sz[i] = 1;
    ll comps = n, best = 1;
    while (m--) {
        ll u, v;
        cin >> u >> v;
        if (unite(u, v)) {
            comps--;
            best = max(best, sz[find(u)]);
        }
        cout << comps << ' ' << best << '\n';
    }
}

ChạyInput6 5
1 2
3 4
2 3
1 4
5 6

Output5 2
4 2
3 4
3 4
2 4

Độ phức tạp: mỗi cạnh $O(\alpha(n))$.

Thêm cạnh theo ngưỡng

Nhiều câu hỏi có dạng “chỉ dùng các cạnh trọng số không quá $q$ thì …”. Khi mọi câu hỏi biết trước, sắp cạnh tăng theo trọng số và sắp câu hỏi tăng theo ngưỡng. Quét ngưỡng tăng dần: thêm mọi cạnh có trọng số không vượt ngưỡng hiện tại, rồi trả lời.

Mỗi cạnh được thêm đúng một lần, nên ngoài phần sắp xếp $O((m + q) \log)$ thì gần tuyến tính. Đây cũng là cách Kruskal dựng cây khung nhỏ nhất.

Khi gộp hai nhóm kích thước $a$ và $b$, số cặp đỉnh mới liên thông là $a \cdot b$; cộng dồn được số cặp liên thông mà không phải đếm lại từ đầu.

Chạy ngược thời gian

DSU không tách được nhóm. Nhưng nếu mọi lần xóa biết trước, đọc thời gian theo chiều ngược lại: bắt đầu từ trạng thái sau lần xóa cuối, rồi lần lượt thêm các cạnh theo thứ tự ngược với thứ tự xóa. Đáp án sau lần xóa thứ $i$ chính là trạng thái ngay trước khi thêm lại cạnh thứ $i$. Cách này dùng được cho xóa đỉnh, xóa phần tử của dãy, hay những ô bị chặn dần trên lưới. Khi xóa và thêm đan xen tùy ý, cần DSU có hoàn tác chia để trị theo thời gian (bài 7.5).

Ví dụNhững Cây Cầu Sụp Dần

Đề. Đồ thị $N \le 10^5$ đỉnh, $M \le 10^5$ cạnh, ban đầu liên thông. Các cạnh bị xóa theo thứ tự input. Sau mỗi lần xóa, in số cặp đỉnh không còn đường đi tới nhau.

Lời giải. DSU gộp được nhưng không tách được, nên ta chạy ngược thời gian: xóa cạnh theo thứ tự xuôi chính là thêm cạnh theo thứ tự ngược. Sau khi xóa hết, không cặp nào liên thông: $\binom{N}{2}$ cặp bị chia cách. Thêm lại một cạnh nối hai nhóm kích thước $a$ và $b$ làm $a \cdot b$ cặp liên thông trở lại. Với ví dụ, sau khi xóa cạnh thứ hai thì đỉnh 2 bị cô lập: 4 cặp chứa nó bị chia cách.

Bước 1: trạng thái cuối. Mọi cặp bị chia cách, cur $= \binom{N}{2}$; đáp án có thể tới $5 \cdot 10^9$ nên dùng ll.

ll cur = n * (n - 1) / 2;

Bước 2: thêm cạnh ngược thời gian. Sau lần xóa thứ $i$, các cạnh còn lại chính là các cạnh $i + 1..M$. Vì vậy duyệt $i$ từ $M$ về 1: ghi đáp án thứ $i$ trước (lúc đó đã thêm lại đúng các cạnh $i + 1..M$), rồi mới thêm lại cạnh $i$.

for (ll i = m; i >= 1; i--) {
    ans[i] = cur;
    ll u = find(a[i]), v = find(b[i]);
    if (u == v) continue;
    if (sz[u] < sz[v]) swap(u, v);
    cur -= sz[u] * sz[v];
    par[v] = u;
    sz[u] += sz[v];
}

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

const ll N = 1e5 + 5;
ll n, m, par[N], sz[N], a[N], b[N], ans[N];

ll find(ll u) {
    return par[u] == u ? u : par[u] = find(par[u]);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= n; i++) par[i] = i, sz[i] = 1;
    for (ll i = 1; i <= m; i++) cin >> a[i] >> b[i];
    ll cur = n * (n - 1) / 2;
    for (ll i = m; i >= 1; i--) {
        ans[i] = cur;
        ll u = find(a[i]), v = find(b[i]);
        if (u == v) continue;
        if (sz[u] < sz[v]) swap(u, v);
        cur -= sz[u] * sz[v];
        par[v] = u;
        sz[u] += sz[v];
    }
    for (ll i = 1; i <= m; i++) cout << ans[i] << '\n';
}

ChạyInput5 6
1 2
2 3
1 3
3 4
4 5
3 5

Output0
4
7
7
9
10

Độ phức tạp: mỗi cạnh $O(\alpha(N))$.

Độ lệch

Gắn cho mỗi đỉnh một số dif[u], bằng “giá trị” của $u$ trừ giá trị của cha. Lần theo đường đi tới gốc và cộng dồn, ta được độ lệch của $u$ so với gốc; nén đường đi vẫn làm được, chỉ cần cộng dồn dif trước khi nối thẳng vào gốc. Hai đỉnh cùng nhóm thì hiệu giá trị của chúng là hiệu hai độ lệch so với gốc chung, xác định hoàn toàn.

Ràng buộc $x_v - x_u = D$: nếu $u, v$ đã cùng nhóm, kiểm hiệu độ lệch có bằng $D$ không; nếu khác nhóm, nối gốc $r_v$ vào gốc $r_u$ với dif[rv] chọn sao cho ràng buộc đúng, tức $D + \mathrm{dif}[u] - \mathrm{dif}[v]$ khi dif đã là độ lệch so với gốc. Thay phép cộng bằng XOR là ràng buộc “cùng/khác” trên hai trạng thái (tô hai màu, bài 3.1), thay bằng cộng modulo 3 là quan hệ vòng ba nhóm.

ll find(ll u) {
    if (par[u] == u) return u;
    ll r = find(par[u]);
    dif[u] += dif[par[u]];
    return par[u] = r;
}

Ví dụHệ Phương Trình Vị Trí

Đề. $N \le 10^5$ biến nguyên trong $[0, 10^9]$ và $M \le 2 \cdot 10^5$ phương trình $x_R - x_L = D$ với $0 \le D \le 10^4$. In Yes nếu hệ có nghiệm, ngược lại No.

Lời giải. DSU có độ lệch: dif[u] là $x_u - x_{\mathrm{par}(u)}$, và sau find(u) thì dif[u] là $x_u$ trừ giá trị của gốc. Xử lý từng phương trình; gặp phương trình trong cùng nhóm mà hiệu không khớp thì hệ vô nghiệm. Không mâu thuẫn thì luôn chọn được nghiệm trong miền: trong một nhóm, hai biến bất kỳ nối nhau bởi đường đi qua không quá $N - 1$ phương trình, nên chênh lệch không quá $10^5 \cdot 10^4 = 10^9$; dịch cả nhóm để biến nhỏ nhất bằng 0. Với ví dụ, bốn phương trình đầu cho $x_5 - x_1 = 16$, trái với phương trình cuối.

Bước 1: find cộng dồn độ lệch. Tìm gốc của cha trước; lúc đó dif[par[u]] đã là độ lệch của cha so với gốc, cộng nó vào dif[u] rồi nối $u$ thẳng vào gốc.

ll find(ll u) {
    if (par[u] == u) return u;
    ll r = find(par[u]);
    dif[u] += dif[par[u]];
    return par[u] = r;
}

Bước 2: một phương trình $x_r - x_l = d$. Cùng nhóm thì kiểm dif[r] - dif[l] == d. Khác nhóm thì nối gốc $b$ (của $r$) vào gốc $a$ (của $l$) với độ lệch $w$ chọn sao cho sau khi nối $x_r - x_l = d$: $x_r - x_a = w + \mathrm{dif}[r]$ và $x_l - x_a = \mathrm{dif}[l]$, nên $w = d + \mathrm{dif}[l] - \mathrm{dif}[r]$. Nếu theo kích thước phải nối ngược ($a$ vào $b$) thì độ lệch đổi dấu.

ll a = find(l), b = find(r);
if (a == b) {
    if (dif[r] - dif[l] != d) ok = 0;
    continue;
}
ll w = d + dif[l] - dif[r];
if (sz[a] < sz[b]) {
    swap(a, b);
    w = -w;
}
par[b] = a;
dif[b] = w;
sz[a] += sz[b];

Độ lệch tới $10^9$, cộng nhiều lần vẫn vừa long long.

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

const ll N = 1e5 + 5;
ll n, m, par[N], sz[N], dif[N];

ll find(ll u) {
    if (par[u] == u) return u;
    ll r = find(par[u]);
    dif[u] += dif[par[u]];
    return par[u] = r;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= n; i++) par[i] = i, sz[i] = 1;
    bool ok = 1;
    while (m--) {
        ll l, r, d;
        cin >> l >> r >> d;
        ll a = find(l), b = find(r);
        if (a == b) {
            if (dif[r] - dif[l] != d) ok = 0;
            continue;
        }
        ll w = d + dif[l] - dif[r];
        if (sz[a] < sz[b]) {
            swap(a, b);
            w = -w;
        }
        par[b] = a;
        dif[b] = w;
        sz[a] += sz[b];
    }
    cout << (ok ? "Yes" : "No") << '\n';
}

ChạyInput5 5
1 2 4
2 3 7
3 4 3
4 5 2
1 5 15

OutputNo

Độ phức tạp: mỗi phương trình $O(\alpha(N))$.

Nhỏ vào lớn

Mỗi nhóm thường mang theo dữ liệu riêng: tập nhãn, danh sách đỉnh, các giá trị lớn nhất. Khi gộp, đổ từng phần tử của nhóm nhỏ vào nhóm lớn. Một phần tử bị chuyển thì nhóm chứa nó ít nhất gấp đôi, nên mỗi phần tử bị chuyển không quá $\log_2 n$ lần: tổng $O(n \log n)$ lần chuyển, nhân thêm chi phí của map hay set nếu dùng. Đó cũng là lý lẽ của gộp theo kích thước, áp lên dữ liệu thay vì độ sâu cây.

Ví dụThống Kê Nhãn Trong Nhóm

Đề. $N \le 2 \cdot 10^5$ phần tử, phần tử $i$ có nhãn $C_i$, ban đầu đứng riêng. $Q \le 2 \cdot 10^5$ thao tác: gộp nhóm của $a$ và $b$, hoặc hỏi nhóm chứa $x$ có bao nhiêu phần tử nhãn $y$.

Lời giải. Mỗi gốc giữ một map từ nhãn tới số lượng của cả nhóm. Gộp hai nhóm thì đổ map nhỏ hơn vào map lớn hơn (gộp nhỏ vào lớn). Mỗi mục bị chuyển thì map chứa nó lớn ít nhất gấp đôi, nên một mục bị chuyển không quá $\log_2 N$ lần. Với ví dụ, sau khi gộp $\{1, 3\}$, map của nhóm có nhãn 1 xuất hiện 2 lần.

Bước 1: khởi tạo. Mỗi phần tử là một nhóm riêng với map một mục.

for (ll i = 1; i <= n; i++) {
    ll c;
    cin >> c;
    par[i] = i;
    cnt[i][c] = 1;
}

Bước 2: gộp nhỏ vào lớn. Gốc nào có map lớn hơn thì giữ làm gốc mới, để dữ liệu luôn nằm ở gốc; map nhỏ xóa đi sau khi đổ.

ll u = find(x), v = find(y);
if (u == v) continue;
if (cnt[u].size() < cnt[v].size()) swap(u, v);
for (pair<ll, ll> p : cnt[v]) cnt[u][p.first] += p.second;
cnt[v].clear();
par[v] = u;

Bước 3: câu hỏi. Tra map của gốc; dùng count trước để không tạo mục rỗng mới trong map.

ll u = find(x);
cout << (cnt[u].count(y) ? cnt[u][y] : 0) << '\n';

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

const ll N = 2e5 + 5;
ll n, q, par[N];
map<ll, ll> cnt[N];

ll find(ll u) {
    return par[u] == u ? u : par[u] = find(par[u]);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    for (ll i = 1; i <= n; i++) {
        ll c;
        cin >> c;
        par[i] = i;
        cnt[i][c] = 1;
    }
    while (q--) {
        ll t, x, y;
        cin >> t >> x >> y;
        if (t == 1) {
            ll u = find(x), v = find(y);
            if (u == v) continue;
            if (cnt[u].size() < cnt[v].size()) swap(u, v);
            for (pair<ll, ll> p : cnt[v]) cnt[u][p.first] += p.second;
            cnt[v].clear();
            par[v] = u;
        } else {
            ll u = find(x);
            cout << (cnt[u].count(y) ? cnt[u][y] : 0) << '\n';
        }
    }
}

ChạyInput6 8
1 2 1 3 2 1
2 1 2
1 1 3
2 1 1
1 2 5
1 1 2
2 5 1
2 4 3
2 4 1

Output0
2
2
1
0

Độ phức tạp: tổng $O(N \log N \cdot \log N)$: mỗi mục chuyển $O(\log N)$ lần, mỗi lần một thao tác map $O(\log N)$.

Nhảy qua phần tử xong

Trên một dãy, có những phần tử khi đã “xong” (bình đã đầy, ô đã tô, chỗ đã có người) thì không bao giờ được xét lại. Cho mỗi phần tử xong trỏ sang phần tử bên phải, par[i] = i + 1, còn phần tử chưa xong trỏ về chính nó; find(i) khi đó là phần tử chưa xong đầu tiên từ $i$ trở đi. Thêm một ô lính canh $n + 1$ không bao giờ xong. Nén đường đi làm các chuỗi phần tử đã xong bị nhảy qua một bước, và mỗi phần tử chỉ chuyển sang xong một lần, nên tổng chi phí gần tuyến tính. Đây là cách tô màu các đoạn “chỉ tô ô chưa tô” trong $O(n \alpha(n))$.

Ví dụDãy Bình Tràn

Đề. $n \le 2 \cdot 10^5$ bình xếp từ trên xuống, bình $i$ dung tích $a_i$. Đổ $x$ đơn vị vào bình $p$: nước làm đầy bình rồi tràn xuống bình kế tiếp, tràn khỏi bình $n$ thì mất. Xen kẽ là câu hỏi lượng nước trong bình $k$; tổng $m \le 2 \cdot 10^5$ thao tác.

Lời giải. Mô phỏng thẳng có thể đi qua cả trăm nghìn bình đầy ở mỗi lần đổ. Dùng DSU để nhảy qua các bình đã đầy: par[i] = i là bình chưa đầy, đầy thì par[i] = i + 1, nên find(p) là bình chưa đầy đầu tiên từ $p$ trở xuống. Ô $n + 1$ là lính canh không bao giờ đầy.

Bước 1: khởi tạo. Mọi bình, kể cả lính canh, đều trỏ vào chính nó.

for (ll i = 1; i <= n + 1; i++) par[i] = i;

Bước 2: một lần đổ. Bắt đầu ở bình chưa đầy đầu tiên, rót tối đa phần còn trống. Bình vừa đầy thì nối sang bình kế, rồi find lại để nhảy qua cả chuỗi bình đầy phía dưới. Vòng dừng khi hết nước hoặc tới lính canh (nước tràn khỏi bình $n$ thì mất).

p = find(p);
while (p <= n && x > 0) {
    ll add = min(x, a[p] - w[p]);
    w[p] += add;
    x -= add;
    if (w[p] == a[p]) par[p] = p + 1;
    p = find(p);
}

Câu hỏi chỉ in w[k], lượng nước đang có trong bình $k$.

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

const ll N = 2e5 + 5;
ll n, m, a[N], w[N], par[N];

ll find(ll u) {
    return par[u] == u ? u : par[u] = find(par[u]);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    for (ll i = 1; i <= n + 1; i++) par[i] = i;
    cin >> m;
    while (m--) {
        ll t;
        cin >> t;
        if (t == 1) {
            ll p, x;
            cin >> p >> x;
            p = find(p);
            while (p <= n && x > 0) {
                ll add = min(x, a[p] - w[p]);
                w[p] += add;
                x -= add;
                if (w[p] == a[p]) par[p] = p + 1;
                p = find(p);
            }
        } else {
            ll k;
            cin >> k;
            cout << w[k] << '\n';
        }
    }
}

+12 dòngChạyInput4
3 5 2 4
9
1 2 4
1 1 5
2 1
2 2
1 2 5
2 3
2 4
1 4 5
2 4

Output3
5
2
4
4

Mỗi lần đổ dừng ở một bình chưa đầy hoặc ở lính canh, và mỗi bình chuyển sang đầy đúng một lần; nhờ nén đường đi, tổng số bước là $O((n + m)\,\alpha(n))$.