1. Giới thiệu bài toán

Bài toán được phát biểu chi tiết tại VNOI - sqrt2_a. Tóm tắt như sau:

Cho một đồ thị vô hướng gồm ~n~ đỉnh và ~m~ cạnh ban đầu. Sau đó có ~k~ truy vấn, mỗi truy vấn thuộc một trong hai loại:

1. Thêm cạnh ~(a, b)~.
2. Xóa cạnh ~(a, b)~ (dữ liệu đảm bảo cạnh đang tồn tại).

Nhiệm vụ: sau mỗi truy vấn (và cả trước khi xử lý truy vấn nào), hãy in ra số thành phần liên thông của đồ thị.

Ràng buộc: ~(2 \le n \le 10^5), (1 \le m, k \le 10^5)~

Tổng số thao tác ~q = m + k~ cũng có thể lên tới ~2 \times 10^5~.

Đây là bài toán đồ thị động (dynamic graph) với cả hai thao tác thêm và xóa cạnh. Do kích thước lớn, cần những phương pháp tối ưu.

2. Các hướng tiếp cận

2.1. Hướng tiếp cận ngây thơ – BFS/DFS sau mỗi truy vấn

Ý tưởng:
Mỗi khi có thay đổi (thêm hoặc xóa cạnh), ta duyệt lại toàn bộ đồ thị bằng BFS hoặc DFS để đếm số thành phần liên thông.

Độ phức tạp:
Mỗi lần duyệt mất ~O(n + m')~ với ~m'~ là số cạnh hiện tại. Có ~q~ truy vấn, tổng độ phức tạp ~O(q \cdot (n + q))~ trong trường hợp xấu nhất.
Với ~n, q \le 2\times 10^5~, cách này quá chậm, không khả thi.

2.2. Hướng tiếp cận DSU cho trường hợp không có xóa

Nếu chỉ có thêm cạnh (đồ thị chỉ tăng dần), ta dùng Disjoint Set Union (DSU) rất hiệu quả:
Mỗi lần thêm cạnh, nếu hai đỉnh chưa cùng thành phần, ta hợp nhất và giảm số thành phần đi 1.
Độ phức tạp gần như ~O(1)~ cho mỗi thao tác.

Nhưng khi có xóa, DSU cơ bản không hỗ trợ tách rời các thành phần. Điều này đòi hỏi các kỹ thuật nâng cao hơn.

2.3. Hướng tiếp cận ~O(q \sqrt{q})~ – Chia nhóm truy vấn

Nguồn tham khảo: Editorial chính thức của đề bài

Phương pháp này dựa trên ý tưởng phân hoạch dãy thao tác thành các khối (block) có kích thước xấp xỉ ~\sqrt{q}~. Mỗi khối được xử lý độc lập, trong đó tận dụng tính chất: số lượng cạnh thay đổi trạng thái (thêm/xóa) trong một khối là nhỏ, từ đó giảm chi phí xử lý mỗi truy vấn.

2.3.1. Ý tưởng cốt lõi

Chia ~q~ thao tác (gồm ~m~ cạnh ban đầu và ~k~ truy vấn) thành các khối, mỗi khối có ~B = \lceil \sqrt{q} \rceil~ thao tác (có thể điều chỉnh ~B~ để tối ưu thực tế). Khi xét một khối cụ thể, ta phân các cạnh của đồ thị thành hai loại:

• Cạnh tĩnh (static): những cạnh có mặt trong toàn bộ khối, nghĩa là chúng được thêm trước khối và không bị xóa trong khối (hoặc nếu có xóa thì sau khối). Các cạnh này không thay đổi trạng thái trong suốt khối.
• Cạnh động (dynamic): những cạnh có ít nhất một thao tác thêm hoặc xóa nằm trong khối. Số lượng cạnh động trong một khối là ~O(B)~, vì mỗi thao tác trong khối chỉ ảnh hưởng đến một cạnh.

Xử lý một khối gồm ba bước chính:

1. Xây dựng cấu trúc DSU cơ sở chỉ gồm các cạnh tĩnh (có thể dùng path compression để tăng tốc).
2. Với mỗi truy vấn trong khối (theo thứ tự thời gian), ta cập nhật trạng thái của cạnh động tương ứng (thêm hoặc xóa), sau đó thêm tất cả các cạnh động đang tồn tại vào DSU cơ sở (chỉ thêm những cạnh chưa có) và ghi nhận số thành phần liên thông.
3. Sau mỗi truy vấn, ta quay lui (rollback) các thao tác thêm cạnh động vừa thực hiện để DSU trở về trạng thái chỉ có cạnh tĩnh, chuẩn bị cho truy vấn tiếp theo trong khối.

2.3.2. Chi tiết các bước xử lý một khối

Giả sử khối hiện tại bao gồm các thao tác có chỉ số từ ~L~ đến ~R~ (đánh số 1..~q~).

Bước 1: Xác định cạnh tĩnh và cạnh động

• Duyệt tất cả các cạnh đã biết (từ dữ liệu đầu vào). Mỗi cạnh có một khoảng thời gian tồn tại ~[l, r)~ (được xác định từ các cặp thêm/xóa).
• Cạnh được gọi là tĩnh trong khối nếu ~l \le L~ và ~r > R~ (tức nó có mặt trong toàn bộ khối).
• Cạnh được gọi là động nếu nó có giao với khối (~l \le R~ và ~r \ge L~) nhưng không phải là tĩnh.
• Lưu ý: một cạnh có thể không xuất hiện trong khối (khi ~r \le L~ hoặc ~l > R~) – ta bỏ qua.

Bước 2: Xây dựng DSU cơ sở cho khối

• Khởi tạo một DSU có hỗ trợ rollback (sẽ dùng cho cạnh động).
• Duyệt tất cả cạnh tĩnh và thực hiện hợp nhất (union) trên DSU này. Vì các cạnh tĩnh không thay đổi trong khối, ta chỉ cần thực hiện một lần. Có thể dùng path compression để tăng tốc (nhưng phải cẩn thận vì DSU sẽ cần rollback cho cạnh động – thông thường ta dùng hai chế độ: một DSU riêng cho cạnh tĩnh với nén đường, và DSU động không nén để rollback; hoặc dùng chung một DSU nhưng chỉ nén khi thêm cạnh tĩnh và không nén khi thêm cạnh động). Để đơn giản, ta có thể dùng DSU với union by size và không nén đường cho toàn bộ, khi đó mỗi thao tác tốn ~O(\log n)~ – vẫn chấp nhận được.

Bước 3: Xử lý tuần tự từng truy vấn trong khối

Với mỗi truy vấn thứ ~i~ từ ~L~ đến ~R~:

• Cập nhật trạng thái của cạnh liên quan đến truy vấn (nếu là thêm thì đánh dấu cạnh đó đang tồn tại, nếu xóa thì đánh dấu không tồn tại).
• Lấy một snapshot (mốc) của DSU hiện tại (số lượng thay đổi đã lưu trong stack).
• Duyệt qua tất cả cạnh động của khối: nếu cạnh đó đang tồn tại (trạng thái true), thực hiện hợp nhất hai đầu mút của nó trên DSU. Việc hợp nhất này phải được ghi lại để có thể rollback sau.
• Số thành phần liên thông hiện tại của DSU chính là kết quả sau thao tác ~i~.
• Rollback DSU về snapshot đã lưu (xóa tất cả các thay đổi vừa thực hiện do các cạnh động gây ra), đưa DSU về trạng thái chỉ chứa cạnh tĩnh.

Chú ý: Các cạnh động có thể có trạng thái thay đổi theo thời gian trong khối. Việc duyệt lại toàn bộ cạnh động mỗi lần truy vấn (thay vì chỉ cập nhật một cạnh) tuy tốn ~O(B)~ nhưng là chấp nhận được vì ~B~ nhỏ.

2.3.3. Kỹ thuật DSU có rollback

Để thực hiện rollback, DSU không được dùng path compression. Thay vào đó, ta chỉ dùng union by size (hoặc rank). Mỗi lần hợp nhất hai thành phần thành công, ta lưu lại các thông tin thay đổi vào một ngăn xếp (stack), ví dụ: đỉnh con bị đổi cha, kích thước cũ của gốc mới, và số thành phần liên thông trước khi hợp nhất. Khi cần rollback, ta lấy thông tin từ stack và khôi phục lại trạng thái cũ. Mỗi thao tác hợp nhất và rollback đều có chi phí ~O(1)~ (không tính chi phí tìm gốc – nhưng tìm gốc vẫn là ~O(\log n)~ do không nén).

Ngoài ra, để tăng tốc phần xử lý cạnh tĩnh, có thể tách riêng một DSU khác không cần rollback, sử dụng path compression. Khi đó trong mỗi truy vấn, ta sẽ kết hợp kết quả từ DSU tĩnh và các cạnh động tạm thời. Tuy nhiên, việc kết hợp này đòi hỏi phải ánh xạ các đỉnh về đại diện của DSU tĩnh, khá phức tạp. Trong khuôn khổ bài viết, ta giữ cách dùng chung một DSU rollback cho toàn bộ, vì độ phức tạp vẫn đạt yêu cầu.

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

• Số khối: ~\frac{q}{B} \approx \sqrt{q}~.
• Chi phí xây dựng DSU cơ sở mỗi khối: duyệt qua tất cả cạnh để phân loại tĩnh/động và thực hiện union cho cạnh tĩnh. Mỗi cạnh được xét trong mỗi khối mà nó có giao với khối, và mỗi cạnh có thể là tĩnh trong nhiều khối liên tiếp. Tổng số lần xét cạnh trên tất cả các khối là ~O(q \sqrt{q})~ (vì mỗi cạnh với đoạn tồn tại độ dài ~d~ sẽ nằm trong ~O(d/B + 1)~ khối, tổng các ~d~ bằng ~O(q)~, suy ra tổng số lần xét là ~O(q \sqrt{q})~). Chi phí cho mỗi lần xét và union là ~O(\log n)~ (nếu không nén) hoặc ~O(\alpha(n))~ (nếu dùng nén riêng). Vậy tổng chi phí cho bước này là ~O(q \sqrt{q} \log n)~.
• Chi phí xử lý truy vấn trong một khối: mỗi truy vấn phải duyệt qua tất cả cạnh động (số lượng ~O(B)~), thực hiện union (nếu cạnh đang tồn tại) và sau đó rollback. Mỗi union/rollback tốn ~O(\log n)~. Một khối có ~B~ truy vấn, do đó chi phí cho khối là ~O(B^2 \log n)~. Có ~\sqrt{q}~ khối, suy ra tổng chi phí cho bước này là ~O(q \sqrt{q} \log n)~.
• Tổng độ phức tạp: ~O(q \sqrt{q} \log n)~.

Với ~q \le 2 \times 10^5~, ~\sqrt{q} \approx 447~, ~q \sqrt{q} \approx 9 \times 10^7~, nhân với ~\log n \approx 18~ cho khoảng 1,6 tỷ phép toán – lớn nhưng nếu cài đặt tối ưu (C++, dùng mảng tĩnh, tránh cấp phát động) vẫn có thể chạy trong 2-3 giây. Thực tế, hằng số nhỏ hơn do nhiều cạnh không cần xét ở mỗi khối. Nếu muốn an toàn hơn, có thể tăng kích thước khối lên một chút (ví dụ ~B = 700~) để giảm số khối, nhưng khi đó chi phí trong khối tăng lên. Cần cân nhắc.

2.3.5. Lưu ý khi cài đặt

• Chọn kích thước khối: lý thuyết tối ưu là ~B = \sqrt{q}~, nhưng có thể thử ~B = 400~ hoặc ~500~ cho phù hợp với bộ nhớ đệm.
• Xác định nhanh cạnh tĩnh/động: Nên tiền xử lý để biết với mỗi cạnh, khoảng thời gian tồn tại của nó dưới dạng ~[l, r)~ (giống như trong phương pháp segment tree). Sau đó, khi xét khối ~[L, R]~, chỉ cần so sánh ~l, r~ với ~L, R~.
• Quản lý trạng thái hiện tại của cạnh động: Cần một mảng active[edge_id] để biết cạnh đó có đang tồn tại trong đồ thị tại thời điểm đang xét hay không. Mảng này được cập nhật liên tục qua các khối và qua các truy vấn trong khối.
• DSU rollback: Cần lưu stack các thay đổi. Mỗi lần thêm cạnh động thành công, ta push một bản ghi (ví dụ: hai đỉnh, kích thước cũ, ...). Sau truy vấn, rollback đúng số lần đã push.
• Khởi tạo lại DSU cho mỗi khối: Việc xây dựng lại DSU từ đầu cho mỗi khối (bằng cách thêm các cạnh tĩnh) tốn thời gian nhưng không quá lớn. Có thể cải tiến bằng cách chỉ cập nhật DSU giữa các khối nếu tập cạnh tĩnh thay đổi ít, nhưng điều này làm phức tạp code.

2.3.6. Code tham khảo

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

void setupIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

// Cấu trúc đại diện cho một cạnh (luôn đảm bảo u < v để dễ so sánh)
struct Edge {
    int u, v;
    bool operator<(const Edge& other) const {
        if (u != other.u) return u < other.u;
        return v < other.v;
    }
    bool operator==(const Edge& other) const {
        return u == other.u && v == other.v;
    }
};

struct Query {
    int t, id;
};

// Cấu trúc DSU hỗ trợ Rollback
struct DSU {
    int components;
    vector<int> parent;
    vector<int> sz;

    struct State {
        int u, v;
        int sz_u, sz_v;
        int components;
    };
    vector<State> history;

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

    void reset(int n_verts) {
        components = n_verts;
        for(int i = 1; i <= n_verts; ++i) {
            parent[i] = i;
            sz[i] = 1;
        }
        history.clear();
    }

    // Gộp tĩnh: Có Path Compression
    int find_pc(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find_pc(parent[i]);
    }

    void unite_static(int i, int j) {
        int root_i = find_pc(i);
        int root_j = find_pc(j);
        if (root_i != root_j) {
            if (sz[root_i] < sz[root_j]) swap(root_i, root_j);
            parent[root_j] = root_i;
            sz[root_i] += sz[root_j];
            components--;
        }
    }

    // Gộp động: KHÔNG Path Compression để có thể Rollback
    int find_no_pc(int i) {
        while (parent[i] != i) i = parent[i];
        return i;
    }

    void unite_dynamic(int i, int j) {
        int root_i = find_no_pc(i);
        int root_j = find_no_pc(j);

        if (root_i == root_j) {
            history.push_back({-1, -1, -1, -1, components});
            return;
        }

        if (sz[root_i] < sz[root_j]) swap(root_i, root_j);
        history.push_back({root_i, root_j, sz[root_i], sz[root_j], components});

        parent[root_j] = root_i;
        sz[root_i] += sz[root_j];
        components--;
    }

    void rollback() {
        if (history.empty()) return;
        State st = history.back();
        history.pop_back();

        if (st.u != -1) {
            parent[st.v] = st.v; 
            sz[st.u] = st.sz_u;  
            sz[st.v] = st.sz_v;  
            components = st.components; 
        }
    }
};

int main() {
    setupIO();
    int n, m, k;
    if (!(cin >> n >> m >> k)) return 0; // Đọc 3 số nguyên n, m, k 

    vector<Edge> all_edges;
    vector<Edge> initial_edges(m);

    // Đọc m cạnh ban đầu của đồ thị 
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        if (u > v) swap(u, v);
        initial_edges[i] = {u, v};
        all_edges.push_back({u, v});
    }

    vector<Query> queries(k);
    vector<Edge> query_edges(k);

    // Đọc k truy vấn tiếp theo (t=1: thêm cạnh, t=2: xóa cạnh) 
    for (int i = 0; i < k; ++i) {
        int t, u, v;
        cin >> t >> u >> v;
        if (u > v) swap(u, v);
        queries[i] = {t, 0}; 
        query_edges[i] = {u, v};
        all_edges.push_back({u, v});
    }

    // Nén tọa độ cạnh
    sort(all_edges.begin(), all_edges.end());
    all_edges.erase(unique(all_edges.begin(), all_edges.end()), all_edges.end());

    int E = all_edges.size();
    vector<int> U(E), V(E);
    for (int i = 0; i < E; ++i) {
        U[i] = all_edges[i].u;
        V[i] = all_edges[i].v;
    }

    vector<bool> in_graph(E, false);

    // Đánh dấu các cạnh ban đầu đã tồn tại trong đồ thị 
    for (int i = 0; i < m; ++i) {
        int id = lower_bound(all_edges.begin(), all_edges.end(), initial_edges[i]) - all_edges.begin();
        in_graph[id] = true;
    }

    for (int i = 0; i < k; ++i) {
        int id = lower_bound(all_edges.begin(), all_edges.end(), query_edges[i]) - all_edges.begin();
        queries[i].id = id;
    }

    DSU dsu(n);

    // 1. In ra số thành phần liên thông trước khi các thao tác diễn ra 
    for (int i = 0; i < E; ++i) {
        if (in_graph[i]) dsu.unite_static(U[i], V[i]);
    }
    cout << dsu.components << " "; 

    // Bắt đầu xử lý truy vấn theo kỹ thuật Chia căn
    int B = 400; // Kích thước Block (căn bậc hai của 10^5)
    vector<bool> is_dynamic(E, false);

    for (int i = 0; i < k; i += B) {
        int L = i;
        int R = min(k - 1, i + B - 1);

        vector<int> dyn_edges;
        for (int j = L; j <= R; ++j) {
            int id = queries[j].id;
            if (!is_dynamic[id]) {
                is_dynamic[id] = true;
                dyn_edges.push_back(id);
            }
        }

        dsu.reset(n);
        // Xây dựng cây dựa trên các cạnh tĩnh
        for (int j = 0; j < E; ++j) {
            if (in_graph[j] && !is_dynamic[j]) {
                dsu.unite_static(U[j], V[j]);
            }
        }

        // Xử lý từng truy vấn trong block hiện tại
        for (int j = L; j <= R; ++j) {
            int id = queries[j].id;
            int type = queries[j].t;

            // Cập nhật trạng thái cạnh (thêm vào đồ thị nếu t=1, xóa khỏi đồ thị nếu t=2) [cite: 13]
            if (type == 1) in_graph[id] = true;  
            else if (type == 2) in_graph[id] = false;

            int unions_done = 0;
            for (int d_id : dyn_edges) {
                if (in_graph[d_id]) {
                    dsu.unite_dynamic(U[d_id], V[d_id]);
                    unions_done++;
                }
            }

            // 2. In ra số thành phần liên thông sau thao tác biến đổi 
            cout << dsu.components << (j == k - 1 ? "" : " "); 

            for (int c = 0; c < unions_done; ++c) {
                dsu.rollback();
            }
        }

        for (int id : dyn_edges) {
            is_dynamic[id] = false;
        }
    }
    cout << "\n";
    return 0;
}

2.4. Hướng tiếp cận ~O(q \log n \log q)~ – Segment Tree trên thời gian sống của cạnh

Nguồn tham khảo:

• CP-Algorithms: Deleting from a data structure in O(T(n) log n)
• USACO Guide: Offline Deletion

Đây là phương pháp tối ưu và phổ biến nhất cho bài toán đồ thị động với cả thêm và xóa cạnh. Ý tưởng cốt lõi là chuyển bài toán có cả thêm và xóa thành bài toán chỉ có thêm bằng cách xác định khoảng thời gian mà mỗi cạnh tồn tại, sau đó dùng một cấu trúc dữ liệu hỗ trợ thêm và quay lui (rollback) kết hợp với segment tree.

2.4.1. Xác định khoảng thời gian sống của mỗi cạnh

Giả sử ta có ~q~ thao tác (gồm ~m~ cạnh ban đầu và ~k~ truy vấn thêm/xóa). Ta đánh số các thao tác từ ~1~ đến ~q~. Với mỗi cạnh, ta xác định thời điểm nó được thêm vào (lần đầu tiên hoặc sau khi bị xóa) và thời điểm nó bị xóa (nếu có). Như vậy, mỗi cạnh sẽ tồn tại liên tục trong một hoặc nhiều đoạn thời gian. Do mỗi thao tác thêm/xóa đều tạo ra một cặp “thêm – xóa”, ta có thể biểu diễn mỗi cạnh bằng một đoạn ~[l, r)~ với ~l~ là thời điểm thêm, ~r~ là thời điểm xóa (hoặc ~q+1~ nếu không bị xóa). Nếu có nhiều lần thêm/xóa xen kẽ, mỗi lần thêm tạo một đoạn riêng.

Ví dụ:

• Thêm cạnh (1,2) ở thời điểm 2, xóa ở thời điểm 5 → đoạn [2,5)
• Cạnh ban đầu (3,4) không bị xóa → đoạn [1, q+1)

Việc xác định các đoạn này có thể thực hiện bằng cách duyệt qua các thao tác, dùng một map lưu thời điểm thêm gần nhất của mỗi cạnh, khi gặp thao tác xóa thì lấy thời điểm thêm tương ứng và tạo đoạn.

2.4.2. Xây dựng Segment Tree trên trục thời gian

Ta xây dựng một segment tree (cây phân đoạn) trên khoảng thời gian ~[1, q+1)~. Mỗi node của cây đại diện cho một đoạn thời gian. Với mỗi cạnh có đoạn tồn tại ~[l, r)~, ta chèn cạnh đó vào các node của segment tree sao cho đoạn ~[l, r)~ được phủ bởi các node con mà không bị dư thừa. Điều này tương tự như thao tác cập nhật đoạn trên segment tree: ta gọi hàm đệ quy, nếu đoạn của node nằm gọn trong ~[l, r)~ thì thêm cạnh vào node đó; ngược lại, tiếp tục xuống các node con. Nhờ vậy, mỗi cạnh được lưu trong ~O(\log q)~ node.

2.4.3. DSU có khả năng rollback

Vì chúng ta sẽ duyệt cây phân đoạn và thực hiện các thao tác thêm cạnh trên từng node, sau đó cần quay lui để xử lý các nhánh khác, nên DSU thông thường không đáp ứng được. Thay vào đó, ta sử dụng DSU có rollback (còn gọi là DSU với khả năng quay lui). Các đặc điểm của DSU này:

• Không sử dụng path compression (vì nén đường làm thay đổi nhiều liên kết, khó rollback). Chỉ dùng union by size/rank.
• Mỗi lần hợp nhất thành công, ta lưu lại các thay đổi vào một stack: ví dụ, khi gắn gốc ~a~ vào gốc ~b~, ta lưu (a, parent[a] cũ) và (b, size[b] cũ). Sau đó thực hiện gắn và cập nhật size.
• Hàm rollback() sẽ pop hai phần tử khỏi stack và khôi phục lại trạng thái trước khi hợp nhất.
• Ta cũng có thể lấy một snapshot (độ dài stack hiện tại) và rollback về snapshot đó.

Độ phức tạp của mỗi thao tác unite/rollback là ~O(\log n)~ (do chỉ dùng union by size và không nén).

2.4.4. Duyệt Segment Tree để trả lời truy vấn

Sau khi đã chèn tất cả các cạnh vào segment tree, ta thực hiện duyệt cây theo chiều sâu (DFS) từ node gốc, với một DSU rollback toàn cục.

void dfs(node, l, r) {
    snapshot = dsu.snapshot();
    for (cạnh trong node) {
        dsu.unite(u, v);               // thêm các cạnh của node này
    }
    if (l+1 == r) {                    // node lá, tương ứng thời điểm l
        ans[l] = dsu.components;       // ghi nhận số thành phần liên thông
    } else {
        int mid = (l+r)/2;
        dfs(node*2, l, mid);
        dfs(node*2+1, mid, r);
    }
    dsu.rollback_to(snapshot);         // quay lui để trả về trạng thái trước khi vào node
}

Giải thích:

• Khi xuống một node, ta thực hiện tất cả các union ứng với các cạnh được lưu tại node đó.
• Nếu node lá (ứng với một thời điểm cụ thể), lúc đó DSU đã chứa tất cả các cạnh có hiệu lực tại thời điểm đó (vì mọi cạnh có đoạn thời gian chứa thời điểm này đều đã được thêm ở một node tổ tiên nào đó).
• Sau khi xử lý xong node con, ta rollback về trạng thái trước khi thêm các cạnh của node hiện tại, để các nhánh khác không bị ảnh hưởng.

Kết thúc quá trình, mảng ans chứa số thành phần liên thông sau mỗi thao tác (tại các thời điểm từ 1 đến q). Bài toán yêu cầu in trạng thái ban đầu (sau m cạnh ban đầu) và sau mỗi truy vấn tiếp theo, ta chỉ cần lấy các giá trị tương ứng.

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

• Mỗi cạnh được chèn vào ~O(\log q)~ node của segment tree.
• Tổng số lần gọi unite trong quá trình duyệt DFS là tổng số lần cạnh xuất hiện trong các node, tức ~O((m+k) \log q)~.
• Mỗi unite có chi phí ~O(\log n)~ do tìm gốc (không nén) và thao tác rollback cũng tốn ~O(\log n)~.
• Do đó tổng độ phức tạp: ~O((m+k) \log q \log n)~. Với ~n, m, k \le 2\times 10^5~, thuật toán chạy rất nhanh trong thời gian cho phép.

2.4.6. Lưu ý khi cài đặt

• Không dùng path compression: Vì nén đường sẽ thay đổi nhiều liên kết, không thể rollback hiệu quả. Chỉ dùng union by size để đảm bảo độ phức tạp ~O(\log n)~ cho find.
• Xử lý cạnh vô hướng: Cần chuẩn hóa thứ tự hai đỉnh (ví dụ u < v) để việc lưu trong map được nhất quán.
• Chú ý chỉ số: Nên dùng đoạn [1, q+1) để dễ quản lý, trong đó q+1 là thời điểm “sau thao tác cuối”.
• Stack rollback: Cần đảm bảo mỗi unite thành công lưu đúng hai thay đổi, và khi rollback phải lấy đúng hai phần tử. Có thể dùng cấu trúc struct chứa loại thay đổi (parent hay size) hoặc lưu chung trong một mảng cặp.
• Không gian bộ nhớ: Segment tree cần lưu danh sách cạnh tại mỗi node. Số lượng cạnh được lưu là ~O((m+k) \log q)~, với ~q \le 2\times 10^5~ thì bộ nhớ khoảng vài chục MB, hoàn toàn chấp nhận được.

2.4.7. Code tham khảo

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

// Cấu trúc DSU hỗ trợ rollback (không dùng path compression)
struct DSUWithRollback {
    vector<int> parent, sz;   // parent và size (union by size)
    int comps;                 // số thành phần liên thông hiện tại

    // Lưu lịch sử thay đổi để rollback
    struct Change {
        int v;        // đỉnh bị thay đổi
        int old;      // giá trị cũ (parent cũ hoặc size cũ)
        bool is_parent; // true nếu thay đổi parent, false nếu thay đổi size
    };
    stack<Change> history;

    DSUWithRollback(int n) : parent(n+1), sz(n+1, 1), comps(n) {
        for (int i = 1; i <= n; ++i) parent[i] = i;
    }

    // Tìm đại diện (không nén)
    int find(int x) {
        while (parent[x] != x) x = parent[x];
        return x;
    }

    // Hợp nhất hai đỉnh, trả về true nếu có sự thay đổi
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        // Đảm bảo a có size nhỏ hơn để gắn a vào b
        if (sz[a] > sz[b]) swap(a, b);
        // Lưu thay đổi (push 2 change)
        history.push({a, parent[a], true});   // parent của a
        history.push({b, sz[b], false});      // size của b
        parent[a] = b;
        sz[b] += sz[a];
        --comps;
        return true;
    }

    // Rollback một lần hợp nhất (pop 2 change và tăng comps)
    void rollback() {
        Change sz_ch = history.top(); history.pop(); // size change
        Change p_ch  = history.top(); history.pop(); // parent change
        parent[p_ch.v] = p_ch.old;
        sz[sz_ch.v] = sz_ch.old;
        ++comps;
    }

    // Lấy trạng thái hiện tại (số lượng change đã lưu)
    int snapshot() const {
        return history.size();
    }

    // Rollback về trạng thái snapshot
    void rollback_to(int snap) {
        while ((int)history.size() > snap) rollback();
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;
    int Q = m + k;                     // tổng số thao tác (1-indexed)

    // Đọc tất cả thao tác: (type, u, v)
    vector<tuple<int,int,int>> ops(Q+1);
    for (int i = 1; i <= m; ++i) {
        int u, v; cin >> u >> v;
        ops[i] = {1, u, v};
    }
    for (int i = 1; i <= k; ++i) {
        int t, u, v; cin >> t >> u >> v;
        ops[m+i] = {t, u, v};
    }

    // Xác định khoảng thời gian sống của mỗi cạnh (u,v)
    map<pair<int,int>, int> last_add; // lần thêm gần nhất
    vector<tuple<int,int,int,int>> edges; // u, v, l, r  (tồn tại trong [l, r))
    for (int i = 1; i <= Q; ++i) {
        auto [type, u, v] = ops[i];
        if (u > v) swap(u, v); // chuẩn hóa cạnh vô hướng
        if (type == 1) {       // thêm cạnh
            last_add[{u, v}] = i;
        } else {               // xóa cạnh
            auto it = last_add.find({u, v});
            if (it != last_add.end()) {
                int l = it->second;
                int r = i;
                edges.emplace_back(u, v, l, r);
                last_add.erase(it);
            }
        }
    }
    // Các cạnh còn lại không bị xóa, tồn tại đến hết
    for (auto &[uv, l] : last_add) {
        auto [u, v] = uv;
        edges.emplace_back(u, v, l, Q+1);
    }

    // Xây dựng segment tree trên các thời điểm [1, Q+1)
    int seg_sz = Q + 2;                     // đủ để bao [1, Q+1)
    vector<vector<pair<int,int>>> seg(4 * seg_sz); // mỗi node lưu danh sách cạnh (u,v)

    // Thêm cạnh vào segment tree
    function<void(int,int,int,int,int,int,int)> add_edge = [&](int node, int l, int r, int ql, int qr, int u, int v) {
        if (ql <= l && r <= qr) {
            seg[node].emplace_back(u, v);
            return;
        }
        int mid = (l + r) / 2;
        if (ql < mid) add_edge(node*2, l, mid, ql, qr, u, v);
        if (qr > mid) add_edge(node*2+1, mid, r, ql, qr, u, v);
    };
    for (auto &[u, v, l, r] : edges) {
        if (l < r) {
            add_edge(1, 1, seg_sz, l, r, u, v);
        }
    }

    DSUWithRollback dsu(n);
    vector<int> ans(Q+2, 0); // ans[i] = số thành phần liên thông sau thao tác i

    // Duyệt segment tree theo DFS
    function<void(int,int,int)> dfs = [&](int node, int l, int r) {
        int snap = dsu.snapshot();
        // Thêm tất cả cạnh tại node này
        for (auto &[u, v] : seg[node]) {
            dsu.unite(u, v);
        }
        if (r - l == 1) {       // node lá → ứng với thời điểm l
            ans[l] = dsu.comps;
        } else {
            int mid = (l + r) / 2;
            dfs(node*2, l, mid);
            dfs(node*2+1, mid, r);
        }
        dsu.rollback_to(snap); // khôi phục trạng thái trước khi vào node
    };
    dfs(1, 1, seg_sz);

    // In kết quả: sau m thao tác đầu và sau mỗi truy vấn
    cout << ans[m];
    for (int i = 1; i <= k; ++i) {
        cout << ' ' << ans[m + i];
    }
    cout << '\n';

    return 0;
}