您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

BZOJ 4025 二分圖動態判定：分治 + 可撤銷並查集 (離線動態連通性)

編輯：關於C++

題目大意

給定 n 點圖，m 條邊，每條邊存在於時間區間 (st, ed]。共 T 個時間點。求每個時間點圖是否為二分圖。

約束：n, m, T ≤ 10⁵。

核心技術：分治時間軸 + 可撤銷並查集 (不帶路徑壓縮)

1. 時間分治框架

遞歸函數 solve(L, R, edges) 處理時間區間 [L, R]，edges 為完全覆蓋 [L, R] 的邊集合。
mid = (L+R)/2。對每條邊 e：

若 e.st == L && e.ed == R：在當前區間全程存在，直接加入並查集判斷
若 e.ed ≤ mid：遞歸左半 solve(L, mid, leftEdges)
若 e.st > mid：遞歸右半 solve(mid+1, R, rightEdges)
否則跨中點：拆分為 [L, mid] 和 [mid+1, R] 兩段分別遞歸

2. 並查集維護二分圖性質 (帶權並查集 / 拓撲關係)

為每個點 x 維護：

fa[x]：父節點
dist[x]：到父節點的奇偶性 (0=同色, 1=異色)
rank[x]：秩 (按秩合並)

find(x) 返回根，並累積 dist 到根的奇偶性。
union(x, y)：合併 x、y 並設置它們異色 (邊意味著兩端點不同色)。

3. 奇環檢測

加入邊 (u, v) 時：

若 find(u) != find(v)：合併，設置 dist 使 u, v 異色
若 find(u) == find(v) 且 dist(u) == dist(v)：同色卻有邊 → 奇環 → 非二分圖

4. 可撤銷機制 (棧記錄操作)

分治回溯時需恢復並查集狀態。記錄棧：

合併時：壓入 (x, old_fa, old_dist, y, old_rank?)
回溯時：彈出棧恢復
不使用路徑壓縮：路徑壓縮為均攤 O(α)，分治樹結構上均攤失效，僅用按秩合並保證 O(log n) 高度

完整代碼

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

const int MAXN = 100100;

struct Edge {
    int u, v, l, r;
    Edge() {}
    Edge(int u, int v, int l, int r) : u(u), v(v), l(l), r(r) {}
};

namespace UFS {
    int fa[MAXN], rnk[MAXN], dist[MAXN];
    int stk[MAXN * 4], top = 0; // 負數表示 rank 修改

    void init(int n) {
        for (int i = 1; i <= n; ++i) {
            fa[i] = i; rnk[i] = 0; dist[i] = 0;
        }
        top = 0;
    }

    int find(int x) {
        while (fa[x] != x) x = fa[x];
        return x; // 無路徑壓縮
    }

    int getDist(int x) {
        int d = 0;
        while (fa[x] != x) {
            d ^= dist[x];
            x = fa[x];
        }
        return d;
    }

    void unite(int x, int y, int d) { // d = 1 表示異色
        x = find(x); y = find(y);
        if (x == y) return;
        if (rnk[x] > rnk[y]) swap(x, y);
        if (rnk[x] == rnk[y]) {
            ++rnk[y];
            stk[++top] = -y; // 負數標記 rank 修改
        }
        fa[x] = y;
        dist[x] = d;
        stk[++top] = x;
    }

    void rollback(int targetTop) {
        while (top > targetTop) {
            int op = stk[top--];
            if (op < 0) --rnk[-op];
            else {
                fa[op] = op;
                dist[op] = 0;
            }
        }
    }
}

vector edges;
int ans[MAXN];

void solve(int L, int R, vector& es) {
    int mid = (L + R) >> 1;
    int bottom = UFS::top;
    vector left, right;

    for (auto& e : es) {
        if (e.l == L && e.r == R) {
            int u = e.u, v = e.v;
            int fu = UFS::find(u), fv = UFS::find(v);
            int du = UFS::getDist(u), dv = UFS::getDist(v);
            if (fu != fv) {
                UFS::unite(fu, fv, du ^ dv ^ 1);
            } else if ((du ^ dv ^ 1) & 1) { // 奇環
                for (int i = L; i <= R; ++i) ans[i] = 0;
                UFS::rollback(bottom);
                return;
            }
        } else if (e.r <= mid) {
            left.push_back(e);
        } else if (e.l > mid) {
            right.push_back(e);
        } else {
            left.emplace_back(e.u, e.v, e.l, mid);
            right.emplace_back(e.u, e.v, mid+1, e.r);
        }
    }

    if (L == R) {
        ans[L] = 1;
    } else {
        solve(L, mid, left);
        solve(mid+1, R, right);
    }
    UFS::rollback(bottom);
}

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

    int n, m, T;
    cin >> n >> m >> T;
    UFS::init(n);

    edges.reserve(m);
    for (int i = 0; i < m; ++i) {
        int u, v, st, ed;
        cin >> u >> v >> st >> ed;
        ++st; // 區間 (st, ed] → [st+1, ed]
        if (st <= ed) edges.emplace_back(u, v, st, ed);
    }

    solve(1, T, edges);
    for (int i = 1; i <= T; ++i) {
        cout << (ans[i] ? "Yes" : "No") << '\n';
    }
    return 0;
}