DSU Rollback - Gộp Tập Hợp Có Hoàn Tác

Tác giả: FPTOJ Team
Nội dung tham khảo từ: CP-Algorithms - DSU with Rollback

---

1. Bản chất vấn đề

Bài toán: Kiểm tra liên thông theo thời gian

Cho \(N\) đỉnh, thực hiện \(Q\) truy vấn theo thời gian:

• Type 1: Thêm cạnh \((u, v)\) tại thời điểm \(t\).
• Type 2: Xóa cạnh \((u, v)\) tại thời điểm \(t\).
• Type 3: Kiểm tra \(u\) và \(v\) có liên thông tại thời điểm \(t\) không.

DSU thường không hỗ trợ xóa cạnh (không hoàn tác gộp).

DSU Rollback: Hỗ trợ hoàn tác (undo) thao tác gộp gần nhất \(\Rightarrow\) giải quyết offline bằng Divide & Conquer trên thời gian.

So sánh

Cấu trúc	Gộp	Tìm	Hoàn tác
DSU thường	\(O(\alpha(N))\)	\(O(\alpha(N))\)	Không
DSU Rollback	\(O(\log N)\)	\(O(\log N)\)	\(O(1)\)

---

2. Tư duy cốt lõi

Ý tưởng: Không dùng path compression

DSU Rollback không dùng path compression (vì khó hoàn tác). Thay vào đó, chỉ dùng union by size/rank.

Khi gộp 2 tập, lưu lại: - Đỉnh nào bị thay đổi (root cũ). - Kích thước nào bị thay đổi.

Để hoàn tác: khôi phục root và kích thước.

Trace chi tiết

5 đỉnh: 1, 2, 3, 4, 5

Bước	Thao tác	Gộp	Lưu trạng thái	parent[]	size[]
0	—	—	—	\([1,2,3,4,5]\)	\([1,1,1,1,1]\)
1	Gộp(1,2)	root 2→1	\((2, \text{parent}[2]=2, \text{size}[1]=1)\)	\([1,1,3,4,5]\)	\([2,1,1,1,1]\)
2	Gộp(3,4)	root 4→3	\((4, \text{parent}[4]=4, \text{size}[3]=1)\)	\([1,1,3,3,5]\)	\([2,1,2,1,1]\)
3	Gộp(1,3)	root 3→1	\((3, \text{parent}[3]=3, \text{size}[1]=2)\)	\([1,1,1,3,5]\)	\([4,1,2,1,1]\)
4	Undo bước 3	Khôi phục 3		\([1,1,3,3,5]\)	\([2,1,2,1,1]\)

Kiểm tra liên thông: find(1) == find(4)?

• Trước undo: có (cùng root 1).
• Sau undo bước 3: không (root 1 ≠ root 3).

---

3. Phân tích tính đúng đắn

Tại sao không dùng path compression?

Path compression thay đổi nhiều parent trong 1 lần find. Để hoàn tác, cần lưu tất cả thay đổi → tốn bộ nhớ và thời gian.

Chỉ dùng union by size: mỗi lần gộp chỉ thay đổi 1 parent \(\Rightarrow\) hoàn tác \(O(1)\).

Chiều cao cây

Với union by size (không path compression), chiều cao cây tối đa \(O(\log N)\). Do đó find là \(O(\log N)\).

---

4. Đánh giá độ phức tạp

Thao tác	Thời gian
Find	\(O(\log N)\)
Gộp	\(O(\log N)\)
Hoàn tác	\(O(1)\)

---

Code minh họa

C++Python

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

struct DSU_Rollback {
    vector<int> parent, sz;
    stack<tuple<int,int,int>> history; // (node, old_parent, old_size_node)
    int components;

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

    int find(int v) {
        while (v != parent[v]) v = parent[v];
        return v;
    }

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) {
            history.push({-1, -1, -1}); // đánh dấu không thay đổi
            return false;
        }
        if (sz[a] < sz[b]) swap(a, b);
        // Gộp b vào a
        history.push({b, parent[b], sz[a]});
        parent[b] = a;
        sz[a] += sz[b];
        components--;
        return true;
    }

    void rollback() {
        auto [b, old_parent, old_sz_a] = history.top();
        history.pop();
        if (b == -1) return; // không có thay đổi
        sz[parent[b]] = old_sz_a; // parent[b] vẫn là a tại thời điểm gộp
        parent[b] = old_parent;
        components++;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    DSU_Rollback dsu(n);

    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int u, v;
            cin >> u >> v;
            dsu.unite(u, v);
        } else if (type == 2) {
            dsu.rollback();
        } else {
            int u, v;
            cin >> u >> v;
            cout << (dsu.find(u) == dsu.find(v) ? "YES" : "NO") << "\n";
        }
    }
    return 0;
}

import sys
input = sys.stdin.readline

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

    def find(self, v):
        while v != self.parent[v]:
            v = self.parent[v]
        return v

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

    def rollback(self):
        b, old_parent, old_sz_a = self.history.pop()
        if b == -1:
            return
        self.sz[self.parent[b]] = old_sz_a
        self.parent[b] = old_parent
        self.components += 1

n, q = map(int, input().split())
dsu = DSURollback(n)

for _ in range(q):
    parts = list(map(int, input().split()))
    if parts[0] == 1:
        dsu.unite(parts[1], parts[2])
    elif parts[0] == 2:
        dsu.rollback()
    else:
        print("YES" if dsu.find(parts[1]) == dsu.find(parts[2]) else "NO")

---

5. Bài tập luyện tập trên FPTOJ

Dưới đây là các bài tập giúp bạn rèn luyện kỹ thuật DSU Rollback, từ cơ bản đến nâng cao. Các mã bài đều có dạng dsur-* và được liệt kê trong Problem Set.

5.1. Rollback cơ bản (dsur-basic)

Trong một buổi thực hành cấu trúc dữ liệu, bạn được yêu cầu mô phỏng hệ thống quản lý nhóm. Ban đầu có N phần tử, mỗi phần tử là một nhóm riêng biệt. Có Q thao tác:

• 1 u v: Gộp nhóm chứa u và nhóm chứa v.
• 2: Hoàn tác thao tác gộp gần nhất. Nếu không có thao tác nào để hoàn tác thì bỏ qua.
• 3 u v: Hỏi u và v có đang cùng nhóm không?

Ràng buộc: N, Q ≤ 10⁵.

5.2. Tổng nhóm có rollback (dsur-sum)

Trong ngân hàng dữ liệu, mỗi tài khoản có số dư a[i]. Hệ thống có thể gộp các tài khoản thành nhóm (tổng số dư cộng dồn) và hoàn tác việc gộp. Có Q thao tác:

• 1 u v: Gộp nhóm chứa u và nhóm chứa v.
• 2: Hoàn tác thao tác gộp gần nhất.
• 3 u: In tổng số dư của nhóm chứa u.

Ràng buộc: N, Q ≤ 10⁵, |a[i]| ≤ 10⁹. Yêu cầu lưu thêm thông tin tổng và khôi phục khi rollback.

5.3. Dòng thời gian — Timeline (dsur-timeline)

Một thí nghiệm theo dõi sự kết nối giữa N nút mạng theo thời gian. Có Q sự kiện:

• 1 u v: Nút u và v kết nối với nhau.
• 2 u v: Kết nối giữa u và v bị đứt (đảm bảo đã tồn tại).
• 3 u v: Hỏi u và v có kết nối không?

Xử lý offline bằng Chia để trị trên thời gian (Divide and Conquer on Time) kết hợp DSU Rollback. Đây là bài tập kinh điển để hiểu cách áp dụng D&C vào bài toán dynamic connectivity.

Ràng buộc: N, Q ≤ 10⁵.

5.4. Đồ thị động — Dynamic Connectivity (dsur-online)

Cho đồ thị vô hướng N đỉnh, ban đầu rỗng. Có Q truy vấn:

• add u v: Thêm cạnh (u, v).
• remove u v: Xoá cạnh (u, v).
• query u v: Hỏi u và v có liên thông không?

Giải bài toán Dynamic Connectivity offline bằng Segment Tree trên thời gian kết hợp DSU Rollback: mỗi cạnh tồn tại trong một khoảng thời gian, thêm vào node Segment Tree tương ứng, sau đó DFS để xử lý.

Ràng buộc: N, Q ≤ 10⁵.

5.5. Lưu trữ trạng thái — Persistent DSU (dsur-persistence)

Hệ thống quản lý phiên bản dữ liệu, mỗi thao tác gộp tạo một snapshot mới. Có Q thao tác:

• 1 u v: Gộp hai nhóm, tạo phiên bản mới.
• 2 k: Quay lại phiên bản thứ k (đánh số từ 0).
• 3 u v: Hỏi ở phiên bản hiện tại, u và v có cùng nhóm không?

Không thể dùng rollback đơn thuần vì có thể quay lại phiên bản bất kỳ. Cần duy trì mảng lịch sử kích thước tại mỗi phiên bản, dùng rollbackTo(targetSize).

Ràng buộc: N, Q ≤ 10⁵.

5.6. Số vùng kết nối qua thời gian (dsur-connect)

Trong mạng lưới giao thông N nút, các tuyến đường được xây và phá theo thời gian. Có Q sự kiện:

• connect u v: Xây đường nối u và v.
• disconnect u v: Phá đường (đảm bảo tồn tại).
• count: In số thành phần liên thông hiện tại.

Dùng DSU Rollback mở rộng để lưu thêm biến components, khôi phục khi rollback. Kết hợp với Segment Tree trên thời gian để xử lý.

Ràng buộc: N, Q ≤ 10⁵.

5.7. Đồ thị hai phía động — Dynamic Bipartite (dsur-bipartite)

Đồ thị N đỉnh, ban đầu rỗng. Có Q thao tác:

• add u v: Thêm cạnh.
• remove u v: Xoá cạnh (đảm bảo tồn tại).
• query: Hỏi đồ thị hiện tại có hai phía không?

Sử dụng DSU Rollback mở rộng với parity DSU: ngoài parent và size, lưu thêm parity (chẵn lẻ) để kiểm tra tính hai phía. Khi thêm cạnh nối hai đỉnh cùng parity trong cùng tập → vi phạm.

Ràng buộc: N, Q ≤ 10⁵. Bài tập khó, yêu cầu hiểu sâu về DSU rollback và đồ thị hai phía.

5.8. Cây khung động — Dynamic MST (dsur-mst)

Cho đồ thị N đỉnh, ban đầu không cạnh. Có Q thao tác:

• add u v w: Thêm cạnh (u, v) trọng số w.
• remove u v: Xoá cạnh (u, v) — đảm bảo tồn tại.
• query: In tổng trọng số MST hiện tại. Nếu đồ thị không liên thông, in -1.

Kết hợp D&C trên thời gian với DSU Rollback. Trong mỗi đoạn thời gian, chỉ giữ các cạnh tồn tại suốt đoạn đó, thực hiện Kruskal với các cạnh còn lại.

Ràng buộc: N ≤ 10⁴, Q ≤ 5 × 10⁴. Bài tập khó nhất trong nhóm, yêu cầu thành thạo cả DSU Rollback, Kruskal và D&C trên thời gian.

---

💬 Bình luận