Hướng giải của Hệ Thống Quản Lý Nhóm Nghiên Cứu

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Lời Giải: Hệ Thống Quản Lý Nhóm Nghiên Cứu

Ý tưởng chính

Đây là bài toán DSU Rollback (DSU với khả năng hoàn tác).

DSU thông thường không thể hoàn tác vì path compression thay đổi nhiều con trỏ cùng lúc — rất khó khôi phục.

Giải pháp: Dùng DSU chỉ với Union by Size (bỏ path compression). Mỗi lần gộp, lưu lại đúng 1 thay đổi vào stack lịch sử. Khi rollback, khôi phục đúng 1 thay đổi đó.

Cài đặt chi tiết

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

struct DSU_Rollback {
    vector<int> parent, sz;
    // Lưu lại: (node bị đổi parent, parent cũ, size cũ của root)
    stack<tuple<int,int,int>> history;

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

    int find(int v) {
        while (v != parent[v]) v = parent[v]; // Không path compression
        return v;
    }

    void unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) {
            history.push({-1, -1, -1}); // đánh dấu không đổi gì
            return;
        }
        if (sz[a] < sz[b]) swap(a, b);
        // Gộp b vào a (a lớn hơn hoặc bằng)
        history.push({b, parent[b], sz[a]});
        parent[b] = a;
        sz[a] += sz[b];
    }

    void rollback() {
        if (history.empty()) return;
        auto [b, old_parent, old_sz] = history.top();
        history.pop();
        if (b == -1) return; // không có gì để hoàn tác
        sz[parent[b]] = old_sz;
        parent[b] = old_parent;
    }

    bool same(int u, int v) {
        return find(u) == find(v);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    cin >> n >> q;
    DSU_Rollback dsu(n);
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int u, v; cin >> u >> v;
            dsu.unite(u, v);
        } else if (t == 2) {
            dsu.rollback();
        } else {
            int u, v; cin >> u >> v;
            cout << (dsu.same(u, v) ? "YES" : "NO") << "\n";
        }
    }
}

Phân tích độ phức tạp

  • find: \(O(\log N)\) (không path compression, chỉ union by size → chiều cao cây \(\le \log N\)).
  • unite: \(O(\log N)\).
  • rollback: \(O(1)\).
  • Tổng: \(O(Q \log N)\).

Lưu ý quan trọng

Khi thao tác gộp hai phần tử đã cùng nhóm, ta vẫn phải push {-1,-1,-1} vào stack để đảm bảo rollback lấy đúng thao tác tương ứng (mỗi thao tác 1 ứng với đúng 1 phần tử trên stack).

Nhận xét

Không có ý kiến tại thời điểm này.