Wiki › Cấu trúc dữ liệu › Kết nối động (Dynamic Connectivity)

Kết nối động (Dynamic Connectivity)

Duy trì liên thông khi cạnh được thêm và xóa: offline bằng cây phân đoạn trên thời gian với DSU hoàn tác, online trên rừng bằng Link-Cut Tree hoặc Euler Tour Tree, và thuật toán Holm, de Lichtenberg, Thorup cho đồ thị tổng quát trong O(log² N) khấu hao.

huunguyen huunguyen Updated Tháng 11. 17, 2026 Đọc 27 phút 2 lượt xem

Kết nối động (dynamic connectivity) là bài toán duy trì một đồ thị vô hướng N đỉnh trong khi các cạnh liên tục được thêm và xóa, và phải trả lời nhanh: "u và v có liên thông không?", "đồ thị đang có bao nhiêu thành phần liên thông?". Chỉ có thêm cạnh thì DSU giải xong trong O(α(N)); cái khó nằm ở phép xóa. Chạy lại BFS sau mỗi thao tác tốn O(N+M), còn các kỹ thuật trong trang này đưa chi phí mỗi thao tác xuống O(log2N): offline bằng cây phân đoạn trên trục thời gian, online bằng thuật toán Holm, de Lichtenberg, Thorup (HDT).

Bài toán và bản đồ lời giải

Có ba thao tác: add(u, v), remove(u, v) (có thể có cạnh song song, xóa một bản), connected(u, v) hoặc count() (số thành phần). Lời giải phụ thuộc vào việc ta được biết trước thao tác hay không, và đồ thị có luôn là rừng hay không:

Tình huống Kỹ thuật Chi phí mỗi thao tác
Chỉ thêm cạnh DSU O(α(N))
Thêm và xóa, biết trước mọi thao tác (offline) Cây phân đoạn trên thời gian + DSU hoàn tác O(logKlogN)
Online, đồ thị luôn là rừng (link/cut) Link-Cut Tree hoặc Euler Tour Tree O(logN)
Online, đồ thị tổng quát HDT: phân tầng cạnh + Euler Tour Tree mỗi tầng O(log2N) khấu hao, truy vấn O(logN)
Chỉ thêm cạnh có trọng số, giữ cây khung nhỏ nhất Link-Cut Tree + tính chất chu trình O(logN) khấu hao

Phần lớn bài thi chỉ cần dòng thứ hai (offline). Phần online tổng quát hiếm khi bắt buộc, nhưng ý tưởng của nó rất đáng học vì đây là ví dụ đẹp về phân tích khấu hao bằng "thăng cấp".

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

Vì sao phép xóa khó

Mọi lời giải đều giữ một rừng khung F của đồ thị: hai đỉnh liên thông khi và chỉ khi chúng cùng một cây của F. Cạnh không thuộc F gọi là cạnh ngoài cây (non-tree edge).

  • Xóa một cạnh ngoài cây: F không đổi, chẳng có gì xảy ra.
  • Xóa một cạnh cây (u,v): cây chứa nó vỡ thành Tu và Tv. Nếu còn một cạnh ngoài cây nối Tu với Tv (gọi là cạnh thay thế, replacement edge) thì nối nó vào, số thành phần không đổi; nếu không có thì đồ thị thật sự tách ra.

Toàn bộ độ khó là tìm cạnh thay thế nhanh. Duyệt mọi cạnh ngoài cây quanh Tu có thể tốn O(M) mỗi lần, và người ra đề dễ dàng bắt ta duyệt đi duyệt lại cùng một đống cạnh.

Offline: biến xóa thành hoàn tác

Khi biết trước mọi thao tác, mỗi cạnh "sống" trên một khoảng thời gian [l,r]. Dựng cây phân đoạn trên trục thời gian, đặt mỗi khoảng vào O(logK) nút, rồi DFS: vào nút thì unite các cạnh của nút, tới lá thì trả lời, ra khỏi nút thì rollback. Phép "xóa" tùy ý đã thành phép hoàn tác theo thứ tự ngăn xếp, thứ mà DSU không nén đường đi làm được. Chi tiết, ví dụ chạy tay và code C++ ở trang DSU có hoàn tác (mục "Kết nối động offline"); trang này kèm bản Python ở phần cài đặt.

Một cách offline khác: gán cho mỗi cạnh thời điểm bị xóa làm trọng số và giữ cây khung lớn nhất theo trọng số đó bằng Link-Cut Tree. Khi đó cạnh cây bị xóa luôn là cạnh "già nhất trên chu trình", nên không bao giờ có cạnh thay thế: xóa cạnh cây nghĩa là đồ thị thật sự tách. Mỗi thao tác O(logN).

Nếu đồ thị luôn là rừng (đề đảm bảo link chỉ nối hai cây khác nhau) thì không có cạnh ngoài cây, xóa chỉ là cut. Hai cấu trúc kinh điển:

  • Link-Cut Tree: link, cut, findroot trong O(logN) khấu hao; u,v liên thông khi findroot(u) == findroot(v). Mạnh ở truy vấn trên đường đi (tổng, max trên đường u→v).
  • Euler Tour Tree (ETT): lưu chu trình Euler của mỗi cây (đi qua mỗi cạnh hai lần) thành một dãy trong cây cân bằng (treap hoặc splay). Hai đỉnh liên thông khi nằm cùng một treap. Mạnh ở thông tin của cả cây (kích thước, tổng, "có đỉnh nào được đánh dấu không").

ETT là viên gạch của HDT nên ta xem kỹ. Dãy của một cây gồm một nút cho mỗi đỉnh và hai nút cung (u→v), (v→u) cho mỗi cạnh. Với cây 1−2, 2−3, 2−4:

nút:   [1] (1>2) [2] (2>3) [3] (3>2) (2>4) [4] (4>2) (2>1)

Coi dãy là vòng tròn. Ba thao tác đều là cắt và ghép dãy:

  • reroot(v): xoay vòng để dãy bắt đầu ở nút [v]: tách ngay trước [v] thành AB, ghép lại BA.
  • link(u, v): reroot(u), reroot(v), rồi ghép tour(u)(u→v)tour(v)(v→u).
  • cut(u, v): dãy có dạng A(u→v)B(v→u)C (hoặc ngược thứ tự hai cung). B chính là chu trình của nửa bên kia, AC là nửa còn lại.

Mỗi thao tác là O(1) lần split/merge treap, tức O(logN) kỳ vọng. Một cây k đỉnh có 3k−2 nút, nên kích thước cây đọc được ngay từ số nút ở gốc treap.

Online tổng quát: thuật toán HDT

Holm, de Lichtenberg và Thorup (2001) giải quyết vấn đề "duyệt đi duyệt lại cùng một đống cạnh" bằng một ý rất gọn: mỗi lần duyệt một cạnh mà không dùng được, thăng cấp nó. Cấp chỉ tăng, và có trần ⌊log2N⌋, nên mỗi cạnh chỉ bị duyệt "vô ích" O(logN) lần trong cả đời nó.

Mỗi cạnh e có một cấp ℓ(e)∈[0,⌊log2N⌋], cạnh mới thêm có cấp 0. Gọi Fi là các cạnh cây có cấp ≥i, nên F0⊇F1⊇F2⊇… và F0=F. Mỗi tầng i có một ETT riêng cho rừng Fi. Thuật toán giữ hai bất biến:

  1. Kích thước: mỗi cây của Fi có không quá N/2i đỉnh. (Vì vậy không cần tầng nào trên log2N.)
  2. Rừng tối đại theo cấp: hai đầu của mọi cạnh ngoài cây cấp i liên thông trong Fi. Nói cách khác, F là rừng khung lớn nhất nếu lấy cấp làm trọng số.

Thêm cạnh (u,v): cấp 0. Nếu u,v khác cây trong F0 thì link ở tầng 0, ngược lại ghi nó vào danh sách cạnh ngoài cây cấp 0 của u và v.

Xóa cạnh cây e=(u,v) cấp ℓ: cut nó ở các tầng 0..ℓ, rồi tìm cạnh thay thế từ tầng ℓ đi xuống 0. Tại tầng i:

  1. Gọi Tu,Tv là hai cây của Fi chứa u, v; lấy T là cây nhỏ hơn.
  2. Thăng mọi cạnh cây cấp i của T lên cấp i+1 (link chúng vào Fi+1). Bất biến 1 vẫn đúng: |T|≤12(|Tu|+|Tv|)≤12·N2i.
  3. Duyệt các cạnh ngoài cây cấp i có một đầu trong T. Với cạnh f=(x,y), x∈T:
    • nếu y∉T: f là cạnh thay thế. Biến nó thành cạnh cây cấp i, link ở các tầng 0..i, dừng.
    • nếu y∈T: f vô dụng ở tầng này, thăng nó lên cấp i+1. Bất biến 2 vẫn đúng vì T đã nằm trọn trong Fi+1 sau bước 2.
  4. Không tìm thấy thì xuống tầng i−1. Hết tầng 0 mà vẫn không có thì đồ thị tách thật, số thành phần tăng 1.

Vì sao không bỏ sót cạnh thay thế? Một cạnh thay thế f nếu có cấp >ℓ thì theo bất biến 2, hai đầu của f đã được nối trong Fℓ+1, mà Fℓ+1 không chứa e. Đường nối đó không đi qua e, nên hai đầu của f vẫn cùng phía sau khi cắt e: mâu thuẫn. Vậy mọi cạnh thay thế có cấp ≤ℓ, và khi duyệt từ trên xuống, cạnh tìm được ở tầng cao nhất có thể, đúng điều cần để giữ bất biến 2. Một cạnh thay thế cấp i phải có một đầu trong cây nhỏ hơn của tầng i, vì hai đầu của nó cùng cây Tu∪Tv (bất biến 2) nhưng khác phía.

Vì sao nhanh? Mỗi lần thăng cấp tốn O(logN) (một link ETT hoặc một thao tác trên danh sách kề kèm cập nhật cờ). Một cạnh thăng tối đa log2N lần trong đời, nên tổng chi phí thăng cấp của M cạnh là O(Mlog2N), chia đều cho các lần thêm cạnh. Ngoài thăng cấp, mỗi tầng chỉ tốn thêm O(logN) để tìm T và xử lý cạnh thay thế (cạnh duy nhất không bị thăng), nên mỗi lần xóa tốn thêm O(log2N). Tổng: O(log2N) khấu hao mỗi cập nhật, truy vấn connected chỉ là so gốc treap ở tầng 0, O(logN).

Tìm nhanh "cạnh cấp i trong T": mỗi nút treap ở tầng i giữ hai cờ, và gốc giữ phép OR của cờ trong cả cây con:

  • cờ 1 trên nút đỉnh [x]: x có cạnh ngoài cây cấp i;
  • cờ 2 trên một trong hai nút cung của cạnh cây có cấp đúng bằng i.

Từ gốc treap của T, đi xuống theo nhánh có cờ để lấy từng phần tử cần xử lý trong O(logN), không bao giờ phải duyệt cả T.

Ví dụ chạy tay

Đồ thị 7 đỉnh. Thêm lần lượt 1−2, 2−3, 3−4, 4−5, 5−6, 6−7 (đều thành cạnh cây), rồi 1−3 và 2−6 (hai đầu đã liên thông nên là cạnh ngoài cây). Mọi cạnh có cấp 0; tầng 0 có một cây duy nhất, tầng 1 và 2 chưa có cạnh nào. Bất biến 1: cây tầng 1 có ≤3.5 đỉnh, cây tầng 2 có ≤1.75 đỉnh.

graph
7 8
1 2
2 3
3 4
4 5
5 6
6 7
1 3
2 6
step Rừng F₀ (cạnh cây tô xanh), hai cạnh ngoài cây 1-3 và 2-6 màu xám
highlight blue 1-2 2-3 3-4 4-5 5-6 6-7
highlight gray 1-3 2-6
step Xóa cạnh cây 3-4 (cấp 0): F₀ vỡ thành {1,2,3} và {4,5,6,7}
highlight red 3-4
highlight orange 1 2 3
step Cây nhỏ T = {1,2,3}: thăng 1-2, 2-3 lên cấp 1
highlight purple 1-2 2-3
step Duyệt 1-3: hai đầu đều trong T, vô dụng, thăng lên cấp 1
highlight purple 1-3
step Duyệt 2-6: 6 nằm ngoài T, đây là cạnh thay thế, thành cạnh cây cấp 0
highlight green 2-6

Bảng trạng thái sau khi xóa 3−4 (đúng như chương trình in ra khi chạy trên ví dụ này):

Cạnh Trước Sau khi xóa 3−4 Sau khi xóa thêm 2−6
1−2 cây, cấp 0 cây, cấp 1 cây, cấp 1
2−3 cây, cấp 0 cây, cấp 1 cây, cấp 1
4−5, 5−6, 6−7 cây, cấp 0 cây, cấp 0 cây, cấp 0
1−3 ngoài cây, cấp 0 ngoài cây, cấp 1 ngoài cây, cấp 1
2−6 ngoài cây, cấp 0 cây, cấp 0 (đã xóa)
Số thành phần 1 1 2

Bước xóa 2−6 (cạnh cây cấp 0): F0 lại vỡ thành {1,2,3} và {4,5,6,7}, cây nhỏ là {1,2,3}. Nó không còn cạnh cây cấp 0 nào để thăng, và cũng không còn cạnh ngoài cây cấp 0 nào (cạnh 1−3 đã lên cấp 1 từ lần trước). Hết tầng, kết luận đồ thị tách: 2 thành phần. Để ý lần này thuật toán không phải duyệt lại 1−3: đó chính là chỗ thăng cấp "trả tiền" cho lần duyệt vô ích trước.

Tầng 1 lúc này có cây {1,2,3} với 3 đỉnh, vẫn thỏa ≤3.5. Nếu sau đó thêm 3−7, chương trình in lại 1 thành phần. Toàn bộ chuỗi trên dưới dạng input của chương trình bên dưới:

7 8 3
1 2
2 3
3 4
4 5
5 6
6 7
1 3
2 6
2 3 4
2 2 6
1 3 7

Output: 1 1 2 1.

Cài đặt

Online: HDT với Euler Tour Tree trên treap

Chương trình đọc theo định dạng của bài Kết Nối Động (dynconn): N, M cạnh ban đầu, K thao tác 1 u v (thêm) / 2 u v (xóa một bản), in số thành phần sau trạng thái đầu và sau mỗi thao tác. Lớp DynamicConnectivity hoàn toàn online: dùng được cả khi thao tác sau phụ thuộc câu trả lời trước.

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

// ===== Implicit treap with parent pointers: stores one Euler tour per tree =====
// Node 0 is the null node. Each node is either a vertex node (one per vertex per
// level) or an arc node (two per tree edge per level).
// Flag bit 1: vertex has non-tree edges of this level.
// Flag bit 2: arc of a tree edge whose level is exactly this level.
mt19937 rng(20261116);
vector<int> lc{0}, rc{0}, par{0}, cnt{0}, ident{0};
vector<unsigned> pri{0};
vector<unsigned char> selfFlag{0}, aggFlag{0};
vector<int> freeNodes;

int newNode(int who) {
    int x;
    if (!freeNodes.empty()) { x = freeNodes.back(); freeNodes.pop_back(); }
    else {
        x = lc.size();
        lc.push_back(0); rc.push_back(0); par.push_back(0); cnt.push_back(0);
        ident.push_back(0); pri.push_back(0); selfFlag.push_back(0); aggFlag.push_back(0);
    }
    lc[x] = rc[x] = par[x] = 0; cnt[x] = 1; ident[x] = who;
    pri[x] = rng(); selfFlag[x] = aggFlag[x] = 0;
    return x;
}

void pull(int x) {
    cnt[x] = 1 + cnt[lc[x]] + cnt[rc[x]];
    aggFlag[x] = selfFlag[x] | aggFlag[lc[x]] | aggFlag[rc[x]];
    if (lc[x]) par[lc[x]] = x;
    if (rc[x]) par[rc[x]] = x;
}

int merge(int a, int b) {
    if (!a || !b) return a ? a : b;
    if (pri[a] > pri[b]) { rc[a] = merge(rc[a], b); pull(a); return a; }
    lc[b] = merge(a, lc[b]); pull(b); return b;
}

// a = first k nodes of t, b = the rest
void split(int t, int k, int &a, int &b) {
    if (!t) { a = b = 0; return; }
    if (cnt[lc[t]] < k) {
        int x, y; split(rc[t], k - cnt[lc[t]] - 1, x, y);
        rc[t] = x; pull(t); a = t; b = y;
    } else {
        int x, y; split(lc[t], k, x, y);
        lc[t] = y; pull(t); a = x; b = t;
    }
    par[a] = par[b] = 0;   // writing par[0] is harmless
}

int rootOf(int x) { while (par[x]) x = par[x]; return x; }

int rankOf(int x) {        // number of nodes before x in its sequence
    int r = cnt[lc[x]];
    while (par[x]) {
        if (rc[par[x]] == x) r += cnt[lc[par[x]]] + 1;
        x = par[x];
    }
    return r;
}

void setFlag(int x, unsigned char bit, bool on) {
    if (on) selfFlag[x] |= bit; else selfFlag[x] &= ~bit;
    for (; x; x = par[x]) pull(x);
}

int findFlag(int t, unsigned char bit) {   // requires aggFlag[t] & bit
    while (!(selfFlag[t] & bit)) t = (aggFlag[lc[t]] & bit) ? lc[t] : rc[t];
    return t;
}

// ===== Holm, de Lichtenberg, Thorup =====
struct Edge {
    int u, v, level = 0;
    bool tree = false;
    int posU = -1, posV = -1;              // positions in adj lists (non-tree edges)
    vector<pair<int,int>> arcs;            // arcs[i] = two arc nodes at level i
};

struct DynamicConnectivity {
    int n, levels, components;
    vector<vector<int>> vnode;             // vnode[i][v]
    vector<vector<vector<int>>> adj;       // adj[i][v] = non-tree edges of level i at v
    vector<Edge> edges;

    DynamicConnectivity(int n) : n(n), components(n) {
        levels = __lg(max(n, 1)) + 1;      // levels 0 .. floor(log2 n)
        vnode.assign(levels, vector<int>(n));
        adj.assign(levels, vector<vector<int>>(n));
        for (int i = 0; i < levels; i++)
            for (int v = 0; v < n; v++) vnode[i][v] = newNode(v);
    }

    int treeRoot(int i, int v) { return rootOf(vnode[i][v]); }
    bool connected(int u, int v) { return treeRoot(0, u) == treeRoot(0, v); }

    // rotate the cyclic tour so that it starts at vertex v
    int reroot(int i, int v) {
        int x = vnode[i][v], a, b;
        split(rootOf(x), rankOf(x), a, b);
        return merge(b, a);
    }

    void link(int i, int id) {
        Edge &e = edges[id];
        int a1 = newNode(id), a2 = newNode(id);
        if ((int)e.arcs.size() <= i) e.arcs.resize(i + 1);
        e.arcs[i] = {a1, a2};
        int tu = reroot(i, e.u), tv = reroot(i, e.v);
        merge(merge(merge(tu, a1), tv), a2);   // tour(u) (u,v) tour(v) (v,u)
        if (e.level == i) setFlag(a1, 2, true);
    }

    void cut(int i, int id) {
        auto [a1, a2] = edges[id].arcs[i];
        int r = rootOf(a1), p1 = rankOf(a1), p2 = rankOf(a2);
        if (p1 > p2) { swap(a1, a2); swap(p1, p2); }
        int A, rest, X, B, Y, C;
        split(r, p1, A, rest);
        split(rest, 1, X, rest);
        split(rest, p2 - p1 - 1, B, rest);   // B = tour of one side, stays alone
        split(rest, 1, Y, C);
        merge(A, C);
        freeNodes.push_back(a1); freeNodes.push_back(a2);
    }

    void addNonTree(int id, int i) {
        Edge &e = edges[id];
        e.level = i; e.tree = false;
        e.posU = adj[i][e.u].size(); adj[i][e.u].push_back(id);
        e.posV = adj[i][e.v].size(); adj[i][e.v].push_back(id);
        if (adj[i][e.u].size() == 1) setFlag(vnode[i][e.u], 1, true);
        if (adj[i][e.v].size() == 1) setFlag(vnode[i][e.v], 1, true);
    }

    void eraseFromList(int i, int w, int pos) {
        vector<int> &lst = adj[i][w];
        int moved = lst.back();
        lst[pos] = moved; lst.pop_back();
        if (pos < (int)lst.size()) {
            if (edges[moved].u == w) edges[moved].posU = pos; else edges[moved].posV = pos;
        }
        if (lst.empty()) setFlag(vnode[i][w], 1, false);
    }

    void removeNonTree(int id) {
        Edge &e = edges[id];
        eraseFromList(e.level, e.u, e.posU);
        eraseFromList(e.level, e.v, e.posV);
    }

    int addEdge(int u, int v) {
        int id = edges.size();
        edges.push_back({u, v});
        if (u == v) return id;                     // self-loop never matters
        if (!connected(u, v)) {
            edges[id].tree = true;
            link(0, id);
            components--;
        } else addNonTree(id, 0);
        return id;
    }

    void removeEdge(int id) {
        Edge &e = edges[id];
        if (e.u == e.v) return;
        if (!e.tree) { removeNonTree(id); return; }
        int lv = e.level, u = e.u, v = e.v;
        for (int i = 0; i <= lv; i++) cut(i, id);
        e.arcs.clear(); e.tree = false;

        for (int i = lv; i >= 0; i--) {
            int small = treeRoot(i, u), big = treeRoot(i, v);
            if (cnt[small] > cnt[big]) swap(small, big);

            // 1) push every level-i tree edge of the smaller tree up to level i+1
            while (aggFlag[small] & 2) {
                int x = findFlag(small, 2), g = ident[x];
                setFlag(x, 2, false);
                edges[g].level = i + 1;
                assert(i + 1 < levels);
                link(i + 1, g);
            }
            // 2) scan level-i non-tree edges leaving vertices of the smaller tree
            while (aggFlag[small] & 1) {
                int w = ident[findFlag(small, 1)];
                while (!adj[i][w].empty()) {
                    int g = adj[i][w].back();
                    int other = edges[g].u == w ? edges[g].v : edges[g].u;
                    removeNonTree(g);
                    if (treeRoot(i, other) != small) {   // replacement edge found
                        edges[g].tree = true;
                        edges[g].level = i;
                        for (int j = 0; j <= i; j++) link(j, g);
                        return;
                    }
                    assert(i + 1 < levels);
                    addNonTree(g, i + 1);                // both ends inside: push up
                }
            }
        }
        components++;                                    // no replacement at any level
    }
};

int main() {
    int n, m, k;
    if (scanf("%d %d %d", &n, &m, &k) != 3) return 0;
    DynamicConnectivity dc(n);
    map<pair<int,int>, vector<int>> live;                // (min,max) -> edge ids
    auto add = [&](int u, int v) {
        if (u > v) swap(u, v);
        live[{u, v}].push_back(dc.addEdge(u - 1, v - 1));
    };
    for (int i = 0; i < m; i++) { int u, v; scanf("%d %d", &u, &v); add(u, v); }
    printf("%d", dc.components);
    for (int i = 0; i < k; i++) {
        int t, u, v; scanf("%d %d %d", &t, &u, &v);
        if (t == 1) add(u, v);
        else {
            if (u > v) swap(u, v);
            auto &ids = live[{u, v}];
            dc.removeEdge(ids.back()); ids.pop_back();
        }
        printf(" %d", dc.components);
    }
    printf("\n");
}

Vài điểm then chốt trong code:

  • cut không cần reroot: dãy là vòng tròn nên đoạn nằm giữa hai cung của cạnh luôn là trọn một phía.
  • cnt[root] là số nút treap (3k−2 với cây k đỉnh), so sánh cnt tương đương so sánh số đỉnh, nên chọn được cây nhỏ hơn mà không cần thêm trường.
  • Ở bước 2, phải kiểm tra treeRoot(i, other) != small sau bước 1: bước 1 chỉ sửa tầng i+1 nên gốc treap small ở tầng i không đổi.
  • Cạnh thay thế tìm được ở tầng i được link vào mọi tầng 0..i, vì F0⊇…⊇Fi.

Code đã được đối chiếu với BFS ngây thơ trên 1500 dãy thao tác ngẫu nhiên (có cạnh song song, đỉnh cô lập, N từ 1 tới 40) và cho kết quả trùng với bản offline trên test N=105, 2·105 cạnh tổng cộng (khoảng 2.7 giây, 250 MB).

Offline: cây phân đoạn trên thời gian (Python)

Cùng định dạng input. Bản C++ của cách này có ở trang DSU có hoàn tác; bản Python dưới đây ngắn hơn hẳn HDT và là lựa chọn mặc định khi đề cho offline.

import sys
from collections import defaultdict


def main():
    data = sys.stdin.buffer.read().split()
    n, m, k = int(data[0]), int(data[1]), int(data[2])
    pos = 3
    T = k + 1                               # states 0..k
    open_edges = defaultdict(list)          # (u, v) -> start times of live copies
    intervals = []                          # (l, r, u, v): edge alive in states l..r

    for _ in range(m):
        u, v = sorted((int(data[pos]), int(data[pos + 1]))); pos += 2
        open_edges[(u, v)].append(0)
    for t in range(1, k + 1):
        typ, u, v = int(data[pos]), int(data[pos + 1]), int(data[pos + 2]); pos += 3
        u, v = sorted((u, v))
        if typ == 1:
            open_edges[(u, v)].append(t)
        else:
            start = open_edges[(u, v)].pop()
            intervals.append((start, t - 1, u, v))
    for (u, v), starts in open_edges.items():
        for s in starts:
            intervals.append((s, k, u, v))

    # put each interval on O(log T) segment tree nodes
    seg = [[] for _ in range(4 * T)]

    def insert(node, lo, hi, l, r, e):
        if r < lo or hi < l:
            return
        if l <= lo and hi <= r:
            seg[node].append(e)
            return
        mid = (lo + hi) // 2
        insert(2 * node, lo, mid, l, r, e)
        insert(2 * node + 1, mid + 1, hi, l, r, e)

    for l, r, u, v in intervals:
        insert(1, 0, T - 1, l, r, (u, v))

    parent = list(range(n + 1))
    size = [1] * (n + 1)
    history = []
    comps = [n]
    ans = [0] * T

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

    def dfs(node, lo, hi):
        snap = len(history)
        for u, v in seg[node]:
            a, b = find(u), find(v)
            if a != b:
                if size[a] < size[b]:
                    a, b = b, a
                parent[b] = a
                size[a] += size[b]
                history.append(b)
                comps[0] -= 1
        if lo == hi:
            ans[lo] = comps[0]
        else:
            mid = (lo + hi) // 2
            dfs(2 * node, lo, mid)
            dfs(2 * node + 1, mid + 1, hi)
        while len(history) > snap:          # rollback, newest first
            b = history.pop()
            size[parent[b]] -= size[b]
            parent[b] = b
            comps[0] += 1

    dfs(1, 0, T - 1)
    print(*ans)


main()

Trên ví dụ chạy tay, cả hai chương trình đều in 1 1 2 1.

Độ phức tạp

Cách Thời gian Bộ nhớ
BFS lại sau mỗi thao tác O(K(N+M)) O(N+M)
Offline, cây phân đoạn + DSU hoàn tác O((M+K)logKlogN) O((M+K)logK)
Offline, cây khung lớn nhất theo thời điểm xóa (LCT) O((M+K)logN) khấu hao O(N+M+K)
Online trên rừng (LCT hoặc ETT) O(logN) mỗi thao tác O(N)
Online tổng quát, HDT cập nhật O(log2N) khấu hao, truy vấn O(logN) O(NlogN+M)

Lý giải cho HDT:

  • Thời gian: mỗi thao tác ETT là O(logN) kỳ vọng (treap). Một cạnh thăng cấp tối đa ⌊log2N⌋ lần, mỗi lần O(logN), nên chi phí thăng cấp cả đời của một cạnh là O(log2N), tính gộp vào lần thêm cạnh đó. Phần còn lại của một lần xóa là O(1) thao tác ETT ở mỗi tầng trong O(logN) tầng: O(log2N).
  • Bộ nhớ: mỗi tầng có N nút đỉnh, nên N(⌊log2N⌋+1) nút đỉnh; mỗi cạnh cây cấp ℓ có 2(ℓ+1) nút cung; danh sách kề chứa mỗi cạnh ngoài cây đúng hai lần.

Mở rộng: cây khung nhỏ nhất khi chỉ thêm cạnh

Nếu chỉ thêm cạnh có trọng số và cần giữ cây khung nhỏ nhất (tổng trọng số, hoặc tập cạnh), dùng tính chất chu trình: cạnh nặng nhất trên một chu trình không cần thuộc cây khung nhỏ nhất (xem Cây khung nhỏ nhất). Khi thêm (u,v,w):

  1. u,v khác cây: link, cộng w vào tổng.
  2. Cùng cây: tìm cạnh nặng nhất g trên đường u→v trong cây. Nếu w(g)>w thì cut g, link cạnh mới (tổng thay đổi w−w(g)); ngược lại bỏ qua cạnh mới.

Truy vấn "max trên đường đi" kèm link/cut chính là sở trường của Link-Cut Tree, mỗi cạnh mới tốn O(logN) khấu hao. Mẹo cài đặt: LCT chỉ lưu giá trị trên đỉnh, nên biến mỗi cạnh thành một đỉnh phụ mang trọng số, nối với hai đầu mút. Cùng khung này với "trọng số = thời điểm xóa" (lấy cây khung lớn nhất) cho lời giải offline O(logN) đã nêu ở trên.

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

  • Cạnh song song bị xử lý như một cạnh. Triệu chứng: có hai cạnh 1−2, xóa một cái mà đồ thị tách. Cách tránh: mỗi lần thêm tạo một id cạnh mới, lưu map<cặp đỉnh, danh sách id> và xóa theo id. Bản offline phải ghép +/- của cùng cặp đỉnh theo ngăn xếp hoặc hàng đợi (cách nào cũng đúng vì các bản giống hệt nhau).
  • Khuyên (self-loop) làm hỏng danh sách kề. Cạnh (u,u) bị đẩy hai lần vào cùng một danh sách và vị trí posU, posV đè nhau. Cách tránh: khuyên không ảnh hưởng liên thông, bỏ qua ngay từ đầu (code trên trả về id nhưng không làm gì).
  • Thăng cạnh khi chưa thăng cây. Nếu đẩy cạnh ngoài cây lên cấp i+1 trước khi các cạnh cây của T đã lên Fi+1, bất biến 2 bị vi phạm và về sau sẽ bỏ sót cạnh thay thế (ra sai, không crash). Luôn làm bước 1 trước bước 2.
  • Chọn nhầm cây lớn. Thăng cạnh của cây lớn hơn vẫn ra đáp án đúng ở vài test nhỏ, nhưng phá bất biến 1: cây ở tầng cao vượt N/2i, cấp vượt log2N và truy cập ngoài mảng. Giữ assert(i + 1 < levels) khi debug.
  • Quên link cạnh thay thế ở mọi tầng thấp hơn. Cạnh cấp i phải có mặt trong F0,…,Fi. Chỉ link ở tầng i thì truy vấn connected (đọc ở tầng 0) trả lời sai ngay.
  • Dùng nén đường đi trong bản offline. DSU hoàn tác phải bỏ nén đường đi, chỉ gộp theo kích thước, nếu không rollback khôi phục sai (xem lý do ở DSU có hoàn tác).
  • Khoảng thời gian lệch một. Cạnh bị xóa ở thao tác t sống trên các trạng thái [l,t−1], không phải [l,t]; cạnh không bao giờ bị xóa sống tới trạng thái cuối K. Sai chỗ này cho output lệch đúng tại các thời điểm xóa.
  • Đánh giá thấp hằng số của HDT. O(log2N) với treap và logN tầng ETT chạy chậm hơn bản offline vài lần và tốn bộ nhớ O(NlogN) nút (khoảng 250 MB với N=105 trong code trên). Chỉ dùng HDT khi đề bắt buộc online (ví dụ input bị mã hóa bằng đáp án trước); có thể giảm bộ nhớ bằng cách chỉ tạo nút đỉnh ở tầng i khi đỉnh thật sự có cạnh cấp ≥i.

Biến thể / Mở rộng

  • Chia căn theo thời gian (online, đơn giản hơn HDT): gom B thao tác thành một khối. Các cạnh không bị đụng tới trong khối được gộp sẵn bằng DSU (co thành các siêu đỉnh); trong khối chỉ còn O(B) cạnh "di động" trên đồ thị đã co, mỗi truy vấn duyệt chúng bằng DSU hoàn tác. Với B≈K được O(KK·α). Cách này cần biết trước các thao tác của khối hiện tại; xem thêm Chia căn.
  • Chia để trị offline có co đồ thị: tại mỗi nút thời gian [l,r], co các cạnh sống suốt đoạn, chỉ giữ lại đồ thị kích thước O(số cạnh di động) rồi đệ quy. Kỹ thuật này mở rộng được cho bài toán khó hơn DSU xử lý được, ví dụ đếm cầu động (kết hợp cầu và khớp).
  • Thông tin theo thành phần: DSU hoàn tác (offline) hoặc ETT (online) cùng lúc giữ được kích thước, max, tổng của thành phần. ETT còn hỗ trợ cập nhật giá trị một đỉnh: chỉ cần sửa nút đỉnh đó rồi pull lên gốc.
  • Kiểm tra hai phía động: thay DSU bằng DSU chẵn lẻ có hoàn tác; xem DSU có hoàn tác. Phiên bản online tổng quát cũng làm được theo khung HDT nhưng hiếm khi gặp trong thi.
  • Kỹ thuật xử lý offline nói chung: Xử lý truy vấn offline.

Bài tập luyện

  • Truy vấn kết nối có hoàn tác (dsuroll) (Chuyên gia) thêm cạnh, xóa một bản cạnh song song, hỏi u,v có liên thông: bài nhập môn cho cây phân đoạn trên thời gian.
  • Cây Đũa Phép Cốt Cây Trưởng Lão (elderwand) (Chuyên gia) rừng động với link, cut, tổng trên đường đi và cập nhật điểm: trường hợp "đồ thị luôn là rừng", giải online bằng Link-Cut Tree.
  • Bảo trì mạng (tddn26_netmain) (Chuyên gia) cắm, rút cáp, thay hiệu năng máy và hỏi kích thước cùng max của cụm: kết nối động offline với thông tin theo thành phần, giá trị của đỉnh cũng "sống" theo khoảng thời gian.
  • Kết Nối Động (dynconn) (Chuyên gia) in số thành phần sau mỗi lần thêm/xóa cạnh, có cạnh song song: đúng định dạng của hai chương trình trên trang này. Giới hạn thời gian là 1 giây nên hãy nộp bản offline; bản HDT chạy khoảng 2,7 giây ở test lớn nhất trên máy thử nên nhiều khả năng bị quá thời gian.
  • Bài toán cây khung tuyệt vời (icpc21rega) (Chuyên gia) chỉ thêm cạnh, đếm cạnh thuộc ít nhất một cây khung nhỏ nhất: Link-Cut Tree giữ rừng khung theo thời điểm, thay cạnh "muộn nhất" trên chu trình như mục cây khung nhỏ nhất khi chỉ thêm cạnh.
  • Tô hai màu bảng (icpc25regb) (Bậc thầy) bật/tắt nét đậm trên lưới, quy về đếm cầu trong đồ thị đối ngẫu thay đổi theo thời gian: chia để trị trên thời gian có co đồ thị, vượt ra ngoài khả năng của DSU hoàn tác.
Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0