DSU có hoàn tác (Rollback) và chia để trị offline

DSU có hoàn tác (rollback DSU) là phiên bản DSU cho phép quay lại đúng trạng thái trước đó: gộp vài lần rồi "undo" các lần gộp mới nhất theo thứ tự ngược lại. Mỗi thao tác tốn $O(\log N)$, chậm hơn một chút so với $O(\alpha (N))$ của DSU thường, nhưng đổi lại ta giải được các bài có xóa cạnh hoặc phải thử nhiều tập cạnh khác nhau bằng cách xử lý offline: kết nối động (thêm/xóa cạnh) trong $O((M+K)\log K\log N)$ thay vì dựng lại DSU sau mỗi thao tác tốn $O(K·(N+M+K))$ (có thể tới $M+K$ cạnh cùng sống).

Ý tưởng / Trực giác

DSU thường không xóa được cạnh

DSU chỉ biết gộp. Nếu đề cho "xóa cạnh $(u,v)$", ta không thể tách một tập ra làm hai: DSU không nhớ cạnh nào đã tạo nên tập đó. Cách chữa là đảo góc nhìn: thay vì xóa tùy ý, ta sắp xếp công việc sao cho mọi lần "bỏ cạnh" luôn là bỏ cạnh vừa thêm gần nhất, tức là hoàn tác theo kiểu ngăn xếp (LIFO). Hoàn tác kiểu này thì làm được, miễn là ta ghi lại mỗi lần gộp đã sửa những ô nào.

Vì sao nén đường đi làm hỏng khả năng hoàn tác

Một lần unite với gộp theo kích thước chỉ sửa đúng hai ô: parent[b] = a và sz[a] += sz[b]. Ghi lại $b$ là đủ để hoàn tác. Nhưng nén đường đi thì khác: một lần find có thể sửa parent của hàng loạt đỉnh, và những sửa đổi đó dựa trên các lần gộp mới hơn (những lần sẽ bị hoàn tác). Khi hoàn tác một lần gộp, các con trỏ đã bị nén vẫn trỏ thẳng vào gốc cũ, nên đỉnh bị "kẹt" trong tập mà lẽ ra nó đã rời đi (xem ví dụ ở dưới).

Vì vậy DSU hoàn tác bỏ nén đường đi, chỉ giữ gộp theo kích thước (hoặc hạng). Tính chất quan trọng vẫn còn: một đỉnh chỉ bị tụt sâu thêm một mức khi cây của nó bị treo vào một cây lớn hơn hoặc bằng, tức kích thước tập chứa nó ít nhất gấp đôi. Kích thước không vượt quá $N$ nên độ sâu $\le {\log }_{2}N$, và find chỉ tốn $O(\log N)$ trong trường hợp xấu nhất (không cần phân tích khấu hao).

Ngăn xếp lịch sử

Mỗi lần gộp thành công, đẩy gốc bị treo $b$ vào ngăn xếp history. Muốn quay về trạng thái cũ, ta nhớ độ cao ngăn xếp tại thời điểm đó (gọi là snapshot), rồi pop cho tới khi ngăn xếp về đúng độ cao ấy. Với mỗi $b$ bị pop: gốc cha của nó là $a=$ parent[b] (chưa bị ai sửa, vì không có nén đường đi), trả lại sz[a] -= sz[b] và parent[b] = b.

Điều kiện để đúng: các lần hoàn tác luôn đi theo thứ tự ngược với các lần gộp. Mọi ứng dụng bên dưới (duyệt cây phân đoạn, đệ quy chia để trị) đều tự nhiên có dạng "vào thì gộp, ra thì hoàn tác", đúng thứ tự ngăn xếp.

Ví dụ chạy tay

$N=5$ đỉnh $1.\mathrm{.5}$. Thực hiện unite(1,2), lấy snap, rồi unite(3,4), unite(2,4), cuối cùng rollback(snap). Dấu . là ô sz của đỉnh không phải gốc (không có nghĩa).

Khởi tạo:
  đỉnh:    1  2  3  4  5
  parent:  1  2  3  4  5
  sz:      1  1  1  1  1        history: [ ]

unite(1,2): gốc 1 và 2 cùng size, treo 2 dưới 1
  parent:  1  1  3  4  5
  sz:      2  .  1  1  1        history: [2]

  snap = 1   <- ghi nhớ độ cao ngăn xếp

unite(3,4): treo 4 dưới 3
  parent:  1  1  3  3  5
  sz:      2  .  2  .  1        history: [2, 4]

unite(2,4): find(2) = 1, find(4) = 3, cùng size 2, treo 3 dưới 1
  parent:  1  1  1  3  5
  sz:      4  .  .  .  1        history: [2, 4, 3]

        1           5
       / \
      2   3
          |
          4

Bây giờ rollback(snap = 1): pop cho tới khi ngăn xếp còn 1 phần tử.

pop 3: a = parent[3] = 1, sz[1] = 4 - 2 = 2, parent[3] = 3
  parent:  1  1  3  3  5
  sz:      2  .  2  .  1        history: [2, 4]

pop 4: a = parent[4] = 3, sz[3] = 2 - 1 = 1, parent[4] = 4
  parent:  1  1  3  4  5
  sz:      2  .  1  1  1        history: [2]      <- đúng trạng thái lúc snap

Nếu có nén đường đi thì sao? Giả sử trước khi rollback ta gọi find(4) có nén: đường đi $4\to 3\to 1$ bị nén thành parent[4] = 1. Lúc rollback, pop 3 trả parent[3] = 3, pop 4 lấy $a=$ parent[4] = 1 (sai, lẽ ra là 3), trừ sz[1] thêm 1 thành 1 và để sz[3] = 2. Kết quả: size của cả hai tập đều sai. Tệ hơn, nếu cây của 3 có một đỉnh con $x$ đã treo từ trước snap, và find(x) nén $x$ thẳng lên 1, thì rollback chỉ gỡ 3 khỏi 1 chứ không chạm tới parent[x]: $x$ kẹt lại trong tập của 1 dù lẽ ra phải thuộc tập của 3. Đây chính là lý do phải bỏ nén.

Cài đặt

C++

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

struct RollbackDSU {
    vector<int> parent, sz;
    vector<int> history;      // roots that were attached below another root
    int components;

    RollbackDSU(int n) : parent(n), sz(n, 1), components(n) {
        iota(parent.begin(), parent.end(), 0);
    }

    // No path compression: just climb to the root, depth <= log2(n)
    int find(int x) const {
        while (parent[x] != x) x = parent[x];
        return x;
    }

    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;          // nothing changes, nothing to record
        if (sz[a] < sz[b]) swap(a, b);     // a is the bigger root
        parent[b] = a;
        sz[a] += sz[b];
        components--;
        history.push_back(b);              // enough to undo: parent[b] still is a
        return true;
    }

    int snapshot() const { return history.size(); }

    // Undo every union made after snapshot <!--LCODE28-->, newest first
    void rollback(int snap) {
        while ((int)history.size() > snap) {
            int b = history.back(); history.pop_back();
            int a = parent[b];
            sz[a] -= sz[b];
            parent[b] = b;
            components++;
        }
    }
};

Cách dùng chuẩn luôn là một cặp "chụp, làm, hoàn tác":

int snap = dsu.snapshot();
// ... any number of dsu.unite(...) ...
dsu.rollback(snap);        // DSU is exactly as before

Python

class RollbackDSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.sz = [1] * n
        self.history = []
        self.components = n

    def find(self, x):
        while self.parent[x] != x:     # no path compression
            x = self.parent[x]
        return x

    def unite(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.sz[a] < self.sz[b]:
            a, b = b, a
        self.parent[b] = a
        self.sz[a] += self.sz[b]
        self.components -= 1
        self.history.append(b)
        return True

    def snapshot(self):
        return len(self.history)

    def rollback(self, snap):
        while len(self.history) > snap:
            b = self.history.pop()
            a = self.parent[b]
            self.sz[a] -= self.sz[b]
            self.parent[b] = b
            self.components += 1

Độ phức tạp

Vì sao không thể giữ $O(\alpha (N))$? Cận $\alpha$ của DSU thường là khấu hao nhờ nén đường đi: các lần find đắt "trả trước" cho các lần sau. Khi có hoàn tác, ta có thể quay lại trạng thái cây sâu rồi gọi lại lần find đắt đó bao nhiêu lần cũng được, nên phân tích khấu hao sụp đổ. Chỉ còn cận xấu nhất $O(\log N)$ của gộp theo kích thước.

Ứng dụng 1: Kết nối động offline (cây phân đoạn trên trục thời gian)

Bài toán (như Kết Nối Động (dynconn)): đồ thị $N$ đỉnh, $K$ thao tác thêm/xóa cạnh; sau mỗi thao tác in số thành phần liên thông. Được biết trước toàn bộ thao tác (offline).

Ý tưởng. Đánh số các thời điểm $0,1,\dots ,K$. Mỗi bản sao cạnh sống trong một khoảng liên tục $[\text{thêm},\text{xóa}-1]$ (cạnh không bao giờ bị xóa thì sống tới $K$). Dựng cây phân đoạn trên trục thời gian $[0,K]$ và "rải" mỗi khoảng sống lên $O(\log K)$ nút phủ nó, giống cập nhật đoạn. Sau đó DFS cây phân đoạn:

• Vào nút: snap, gộp mọi cạnh gắn ở nút (chúng sống trên toàn bộ đoạn thời gian của nút).
• Tới lá $t$: DSU lúc này chứa đúng các cạnh sống tại thời điểm $t$ (các cạnh trên đường từ gốc tới lá), ghi đáp án.
• Ra khỏi nút: rollback(snap).

Thứ tự "vào gộp, ra hoàn tác" của DFS đúng là thứ tự ngăn xếp, nên DSU hoàn tác vừa khít.

Ví dụ chạy tay. $N=3$, không có cạnh ban đầu, thao tác: t=1 thêm (1,2); t=2 thêm (2,3); t=3 xóa (1,2).

Khoảng sống:  (1,2): [1, 2]      (2,3): [2, 3]

Trục thời gian:   0     1     2     3
(1,2)                   =======
(2,3)                         =======

Cây phân đoạn trên [0,3], cạnh gắn ở nút:
                    [0,3] {}
                  /          \
           [0,1] {}          [2,3] {(2,3)}
           /     \            /        \
      [0] {}  [1] {(1,2)}  [2] {(1,2)}  [3] {}

DFS (số thành phần sau khi gộp các cạnh của nút):

[0,3]: không có cạnh                comps = 3
  [0,1]:                          comps = 3
    [0]:                          ans[0] = 3
    [1]: +(1,2)                   ans[1] = 2   rollback -> 3
  [2,3]: +(2,3)                   comps = 2
    [2]: +(1,2)                   ans[2] = 1   rollback -> 2
    [3]:                          ans[3] = 2
  rollback (2,3)                  comps = 3

Kết quả: 3 2 1 2

Cài đặt đầy đủ (định dạng vào/ra của dynconn, dùng RollbackDSU ở trên):

int K;                                   // time points are 0..K
vector<vector<pair<int,int>>> seg;       // edges stored at segment tree nodes
vector<int> answer;

// Attach edge e to every node whose range lies inside [ql, qr]
void addEdge(int node, int l, int r, int ql, int qr, pair<int,int> e) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) { seg[node].push_back(e); return; }
    int m = (l + r) / 2;
    addEdge(2 * node, l, m, ql, qr, e);
    addEdge(2 * node + 1, m + 1, r, ql, qr, e);
}

void dfs(int node, int l, int r, RollbackDSU& dsu) {
    int snap = dsu.snapshot();
    for (auto [u, v] : seg[node]) dsu.unite(u, v);   // edges alive on all of [l, r]
    if (l == r) {
        answer[l] = dsu.components;
    } else {
        int m = (l + r) / 2;
        dfs(2 * node, l, m, dsu);
        dfs(2 * node + 1, m + 1, r, dsu);
    }
    dsu.rollback(snap);                               // leave the DSU as we found it
}

int main() {
    int n, m;
    scanf("%d %d %d", &n, &m, &K);
    map<pair<int,int>, vector<int>> openSince;       // edge -> start times of live copies
    vector<array<int,4>> lives;                       // {u, v, from, to}
    auto key = [](int u, int v) { if (u > v) swap(u, v); return make_pair(u, v); };

    for (int i = 0; i < m; i++) {
        int u, v; scanf("%d %d", &u, &v);
        openSince[key(u, v)].push_back(0);
    }
    for (int t = 1; t <= K; t++) {
        int type, u, v; scanf("%d %d %d", &type, &u, &v);
        auto e = key(u, v);
        if (type == 1) {
            openSince[e].push_back(t);
        } else {
            int s = openSince[e].back(); openSince[e].pop_back();
            lives.push_back({e.first, e.second, s, t - 1});   // gone from time t on
        }
    }
    for (auto& [e, starts] : openSince)
        for (int s : starts) lives.push_back({e.first, e.second, s, K});

    seg.assign(4 * (K + 1), {});
    for (auto& [u, v, from, to] : lives)
        addEdge(1, 0, K, from, to, {u - 1, v - 1});

    RollbackDSU dsu(n);
    answer.assign(K + 1, 0);
    dfs(1, 0, K, dsu);
    for (int t = 0; t <= K; t++) printf("%d%c", answer[t], t == K ? '\n' : ' ');
}

Độ phức tạp. Mỗi khoảng sống được rải lên $O(\log K)$ nút, nên tổng số lần gộp là $O((M+K)\log K)$, mỗi lần $O(\log N)$: tổng thời gian $O((M+K)\log K\log N)$. Bộ nhớ $O((M+K)\log K)$ cho danh sách cạnh ở các nút cây phân đoạn.

Ứng dụng 2: Chia để trị trên đáp án đơn điệu

Dạng bài: có hai nhóm cạnh $X_1,X_2,\dots ,X_p$ và $Y_1,Y_2,\dots ,Y_q$ (mỗi nhóm đã sắp theo một tiêu chí nào đó, ví dụ trọng số). Với mỗi $i\in [0,p]$, cần $g(i)$ là số $j$ nhỏ nhất sao cho đồ thị gồm $X_1..X_i$ và $Y_1..Y_j$ thỏa một tính chất đơn điệu theo việc thêm cạnh (ví dụ $s$ và $t$ liên thông); $g(i)=q+1$ nếu không tồn tại.

Thêm cạnh $X$ chỉ làm tính chất dễ đạt hơn, nên $g$ không tăng theo $i$. Đây là mô hình chia để trị trên đáp án đơn điệu (cùng họ với tối ưu DP chia để trị trong trang CDQ): biết $g(i)\in [j_l,j_r]$ với mọi $i\in [i_l,i_r]$, tính $g(mid)$ rồi chia đôi:

i:     i_l ........ mid ........ i_r
g(i):  >= g(mid)    g(mid)    <= g(mid)
       tìm trong [g(mid), j_r]   tìm trong [j_l, g(mid)]

Dựng lại DSU ở mỗi lời gọi thì quá chậm. DSU hoàn tác cho phép giữ bất biến: khi vào solve(il, ir, jl, jr), DSU chứa đúng $X_1..X_{i_l-1}$ và $Y_1..Y_{j_l}$. Mỗi lời gọi chỉ thêm các cạnh "nằm giữa" rồi hoàn tác khi ra.

int p, q, s, t;
vector<pair<int,int>> X, Y;    // X[1..p], Y[1..q], each sorted by its own key
vector<int> g;                 // g[i] for i = 0..p
RollbackDSU* dsu;

// Invariant on entry: DSU holds exactly X[1..il-1] and Y[1..jl]
// Promise: g[i] lies in [jl, jr] for every i in [il, ir]
void solveDC(int il, int ir, int jl, int jr) {
    if (il > ir) return;
    int mid = (il + ir) / 2;

    int snap = dsu->snapshot();
    for (int i = max(il, 1); i <= mid; i++) dsu->unite(X[i].first, X[i].second);
    int j = jl;
    while (j < jr && dsu->find(s) != dsu->find(t)) {
        j++;
        if (j <= q) dsu->unite(Y[j].first, Y[j].second);
    }
    g[mid] = j;                 // j == q + 1 means "never connected"
    dsu->rollback(snap);

    // Left part (fewer X edges) needs at least g[mid] edges of Y
    snap = dsu->snapshot();
    for (int k = jl + 1; k <= min(g[mid], q); k++) dsu->unite(Y[k].first, Y[k].second);
    solveDC(il, mid - 1, g[mid], jr);
    dsu->rollback(snap);

    // Right part (more X edges) needs at most g[mid] edges of Y
    snap = dsu->snapshot();
    for (int i = max(il, 1); i <= mid; i++) dsu->unite(X[i].first, X[i].second);
    solveDC(mid + 1, ir, jl, g[mid]);
    dsu->rollback(snap);
}
// Call: DSU empty, solveDC(0, p, 0, q + 1)

Độ phức tạp. Có $O(\log p)$ tầng đệ quy. Ở mỗi tầng, các đoạn $[i_l,i_r]$ rời nhau nên tổng số cạnh $X$ được thêm là $O(p)$; các đoạn $[j_l,j_r]$ chỉ chồng nhau ở đầu mút nên tổng số cạnh $Y$ là $O(q+p)$. Tổng $O((p+q)\log p)$ lần gộp, mỗi lần $O(\log N)$.

Ứng dụng 3: Kiểm tra hai phía động (DSU chẵn lẻ + hoàn tác)

Đồ thị là hai phía (bipartite) khi tô được hai màu sao cho mọi cạnh nối hai màu khác nhau, tương đương không có chu trình lẻ. Với thêm/xóa cạnh và câu hỏi "hiện tại có hai phía không?", ta dùng lại khung cây phân đoạn thời gian ở Ứng dụng 1, chỉ thay DSU bằng DSU chẵn lẻ: mỗi đỉnh lưu thêm par[x] $=$ màu$(x)\oplus$ màu$(\text{parent}[x])$. Màu tương đối của $x$ so với gốc là XOR các par trên đường lên gốc.

Thêm cạnh $(u,v)$:

• Nếu $u,v$ cùng gốc: hợp lệ khi và chỉ khi màu tương đối $p_u\ne p_v$; ngược lại vừa tạo chu trình lẻ.
• Nếu khác gốc: treo gốc nhỏ $r_v$ dưới gốc lớn $r_u$ với par[rv] $=p_u\oplus p_v\oplus 1$. Kiểm tra: màu$(v)=$ màu$(r_u)\oplus$ par[rv] $\oplus p_v$, nên màu$(u)\oplus$ màu$(v)=p_u\oplus p_u\oplus p_v\oplus 1\oplus p_v=1$, đúng yêu cầu khác màu.

struct ParityDSU {
    vector<int> parent, sz, par;   // par[x] = color(x) XOR color(parent[x])
    vector<int> history;

    ParityDSU(int n) : parent(n), sz(n, 1), par(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }

    // Returns {root, color(x) XOR color(root)}
    pair<int,int> find(int x) const {
        int p = 0;
        while (parent[x] != x) { p ^= par[x]; x = parent[x]; }
        return {x, p};
    }

    // Edge (u, v) forces different colors. Returns false on an odd cycle.
    bool addEdge(int u, int v) {
        auto [ru, pu] = find(u);
        auto [rv, pv] = find(v);
        if (ru == rv) return pu != pv;       // same component: fine iff colors differ
        if (sz[ru] < sz[rv]) { swap(ru, rv); swap(pu, pv); }
        parent[rv] = ru;
        par[rv] = pu ^ pv ^ 1;               // makes color(u) != color(v)
        sz[ru] += sz[rv];
        history.push_back(rv);
        return true;
    }

    int snapshot() const { return history.size(); }

    void rollback(int snap) {
        while ((int)history.size() > snap) {
            int b = history.back(); history.pop_back();
            sz[parent[b]] -= sz[b];
            parent[b] = b;
            par[b] = 0;
        }
    }
};

DFS trên cây phân đoạn có thêm một nhánh cắt: nếu một cạnh ở nút tạo chu trình lẻ thì chu trình đó tồn tại trên toàn bộ đoạn thời gian của nút, nên mọi lá bên dưới đều là "không".

vector<int> ok;   // ok[t] = 1 if the graph at time t is bipartite

void dfs(int node, int l, int r, ParityDSU& dsu) {
    int snap = dsu.snapshot();
    bool good = true;
    for (auto [u, v] : seg[node])
        if (!dsu.addEdge(u, v)) { good = false; break; }
    if (!good) {
        for (int t = l; t <= r; t++) ok[t] = 0;   // odd cycle stays for the whole range
    } else if (l == r) {
        ok[l] = 1;
    } else {
        int m = (l + r) / 2;
        dfs(2 * node, l, m, dsu);
        dfs(2 * node + 1, m + 1, r, dsu);
    }
    dsu.rollback(snap);                          // also on the early-exit path
}

Độ phức tạp giống Ứng dụng 1: $O((M+K)\log K\log N)$ thời gian, $O((M+K)\log K)$ bộ nhớ (vòng gán ok[t] = 0 tổng cộng $O(K)$ vì mỗi lá bị gán nhiều nhất một lần theo nhánh cắt).

⚠️ Lỗi thường gặp

• Giữ lại nén đường đi "cho nhanh". Chỉ cần một dòng parent[x] = find(parent[x]) là rollback sai âm thầm: size lệch, đỉnh kẹt sai tập. Triệu chứng: đúng ví dụ nhỏ, sai test lớn. Cách tránh: find chỉ đọc (khai báo const như code trên), không bao giờ gán parent trong find.

• Quên gộp theo kích thước. Bỏ nén rồi mà còn treo tùy ý thì cây thành chuỗi, find tụt về $O(N)$ và cả thuật toán thành $O(NK)$. Luôn if (sz[a] < sz[b]) swap(a, b).

• Đếm số lần pop theo số lần gọi unite. Lần gộp mà hai đỉnh đã cùng tập không đẩy gì vào ngăn xếp. Nếu hoàn tác bằng "pop đúng số cạnh đã thêm" thì sẽ pop lẹm sang lần gộp của nút cha. Cách tránh: luôn dùng snapshot() lấy độ cao ngăn xếp rồi rollback(snap).

• Quên hoàn tác dữ liệu phụ. Số thành phần, par chẵn lẻ, tổng trọng số của tập... đều phải trả lại trong rollback. Triệu chứng: components trôi dần sau mỗi nhánh DFS.

• Thoát sớm mà không rollback. Ở Ứng dụng 3, khi gặp chu trình lẻ rồi return ngay trước dòng rollback là để lại rác cho nút anh em. Mọi đường ra khỏi hàm đều phải đi qua rollback(snap).

• Sai khoảng sống của cạnh. Cạnh xóa ở thời điểm $t$ chỉ sống tới $t-1$ (off-by-one); cạnh chưa bị xóa phải kéo tới $K$; cạnh ban đầu bắt đầu từ $0$. Cạnh song song (nhiều bản sao cùng $(u,v)$) phải lưu danh sách thời điểm thêm, không dùng một biến duy nhất; và nhớ chuẩn hóa $(u,v)$ với $u<v$ để xóa 2 3 1 khớp với thêm 1 1 3.

• Tưởng hoàn tác được theo thứ tự bất kỳ. DSU hoàn tác chỉ undo theo LIFO. Nếu bài đòi xóa cạnh bất kỳ online (không biết trước thao tác), kỹ thuật này không dùng được; cần cấu trúc khác (ví dụ link-cut tree) hoặc tìm cách đưa về offline.

• Chia để trị khi $g$ không đơn điệu. Ứng dụng 2 chỉ đúng khi thêm cạnh luôn làm tính chất dễ đạt hơn. Kiểm tra kỹ hướng đơn điệu: nửa trái tìm $j$ trong $[g(mid),j_r]$, nửa phải trong $[j_l,g(mid)]$; đảo ngược là sai.

• Tràn bộ nhớ ở cây phân đoạn. Mỗi cạnh rải lên tới $\approx 2{\log }_{2}K$ nút; với $M+K=2·{10}^5$ là vài triệu cặp. Dùng pair<int,int> (không long long) và mảng 4 * (K + 1) nút.

Biến thể / Mở rộng

• DSU không nén + mốc thời gian (DSU "bền" nhẹ). Không cần hoàn tác, chỉ cần hỏi quá khứ: vẫn chỉ gộp theo kích thước, ghi thêm when[b] là thời điểm $b$ bị treo. Hai đỉnh liên thông tại thời điểm $T$ nếu leo lên theo các cạnh cha có when $\le T$ gặp cùng một gốc. Cây nông $O(\log N)$ nên leo trực tiếp là đủ nhanh.
• Hoàn tác cấu trúc khác. Ý tưởng "ghi lại ô đã sửa, pop theo LIFO" dùng được cho mọi cấu trúc mà mỗi thao tác chỉ sửa $O(1)$ (hoặc ít) ô và không có khấu hao: mảng đếm, cơ sở XOR tuyến tính, ... Khung cây phân đoạn thời gian vì vậy còn được dùng cho "thêm/xóa vector, hỏi XOR lớn nhất".
• Liên hệ. DSU cơ bản và nén đường đi xem ở trang DSU; khuôn "vào gộp, ra hoàn tác" trên đệ quy là một dạng chia để trị; các kỹ thuật offline chia đôi theo thời gian khác (CDQ) ở trang CDQ. Nhiều bài Kruskal có truy vấn (xem cây khung nhỏ nhất) cần thử gộp một nhóm cạnh rồi bỏ đi, đúng chỗ của DSU hoàn tác.

Bài tập luyện

Pool CTOJ hiện chưa có bài dễ cho kỹ thuật này; các bài dưới đều ở mức Kỳ cựu trở lên.

Luyện kỹ thuật

Lưu ý: ở mục này, pool hiện chỉ có 2 bài dùng trực tiếp DSU hoàn tác là envy và dynconn; các bài còn lại là bài khởi động hoặc biến thể của kỹ thuật.

• Từ điển của Mahmoud (wordrel) (Kỳ cựu) khởi động cho Ứng dụng 3: DSU chẵn lẻ (đồng nghĩa = cùng màu, trái nghĩa = khác màu) và phát hiện mâu thuẫn; chưa cần hoàn tác nhưng là nền của ParityDSU.
• Cạnh ghen tị (envy) (Chuyên gia) với mỗi truy vấn và mỗi nhóm trọng số, thử gộp các cạnh của truy vấn vào DSU "các cạnh nhẹ hơn" để phát hiện chu trình, rồi hoàn tác ngay trước truy vấn kế tiếp.
• Truy Vấn Đường Mới (newroadsq) (Chuyên gia) biến thể DSU không nén đường đi + mốc thời gian gộp (mục Biến thể): cây nông $O(\log N)$ cho phép leo trực tiếp để tìm ngày đầu tiên hai đỉnh liên thông.
• Kết Nối Động (dynconn) (Chuyên gia) bài chuẩn của Ứng dụng 1: cây phân đoạn trên trục thời gian, mỗi bản sao cạnh sống trong một khoảng, nhớ xử lý cạnh song song.

Đề VOI

• Đi xe buýt (voi20_bus) (Kỳ cựu) VOI 2020: đổi bài toán thành chọn hai ngưỡng giá cho hai công ty; ngưỡng tối ưu của công ty này không tăng khi ngưỡng công ty kia tăng, nên dùng chia để trị trên đáp án đơn điệu với DSU hoàn tác (Ứng dụng 2).