SWJTU OJ 1569：離線並查集（連通性查詢）

問題：動態圖連通性查詢，支持加邊、刪邊、查詢兩點連通。離線算法：時間軸分治 + 並查集可撤銷（或線段樹分治）。

由於原文內容較少，這裡補充標準離線並查集框架：

線段樹分治 + 可撤銷並查集

1. 將每條邊的存在時間區間映射到線段樹節點。
2. DFS 遍歷線段樹：進入節點合併該節點所有邊，遞歸子節點，退出時撤銷合併（需並查集支持回滾：記錄修改棧）。
3. 葉節點對應具體時間點，直接回答查詢。

可撤銷並查集關鍵

struct DSU {
    vector fa, sz;
    vector> history; // 記錄 (被合併根, 原size)
    int find(int x) { return fa[x]==x?x:find(fa[x]); } // 不壓縮路徑！
    bool unite(int x, int y) {
        x=find(x); y=find(y); if (x==y) { history.emplace_back(-1,-1); return false; }
        if (sz[x]>sz[y]) swap(x,y);
        history.emplace_back(x, sz[y]);
        fa[x]=y; sz[y]+=sz[x]; return true;
    }
    void rollback() {
        auto [x, sy] = history.back(); history.pop_back();
        if (x==-1) return;
        int y = fa[x];
        fa[x]=x; sz[y]=sy;
    }
};

時間複雜度 O((Q+M) log Q)，空間 O(Q+M)。適合動態連通性離線查詢。