Codeforces 91C Ski Base 動態加邊計算歐拉回路數 (並查集 + 數學)

問題描述

無向圖初始無邊，依次添加 m 條邊。每加一條邊後，輸出當前圖中歐拉回路（非空邊子集，每點度數為偶數）的個數模 10⁹+9。n,m ≤ 10⁵。

數學核心

設圖有 m 條邊，關聯矩陣 I (m×n)。邊子集形成歐拉回路 ⇔ 對應行向量 XOR 和為零向量。這些零和子集構成線性空間，維數 = m - rank(I)。故方案數 = 2^{m - rank(I)}。
加入新邊 (u,v) 後：
- 若 u,v 已連通，新邊與現有邊線性相關 → rank 不變，m 增 1 → 方案數乘 2。
- 若 u,v 不連通，新邊線性無關 → rank 增 1，m 增 1 → 方案數不變。
初始方案數為 1 (空集)，輸出時減 1 排除空集。

算法：並查集維護連通性

每加一條邊，若兩端點已在同一連通分量，答案乘 2；否則合併分量。答案模 MOD = 1,000,000,009。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000009;
const int MAXN = 100005;

int fa[MAXN];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    fa[x] = y; return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    while (cin >> n >> m) {
        iota(fa+1, fa+n+1, 1);
        long long ans = 1;
        while (m--) {
            int u, v; cin >> u >> v;
            if (!unite(u, v)) ans = (ans * 2) % MOD;
            cout << (ans - 1 + MOD) % MOD << '\n';
        }
    }
    return 0;
}

複雜度

O(m α(n))，極快。空間 O(n)。

關鍵洞察總結

• 歐拉回路計數 ↔ 關聯矩陣零空間維數。
• 加邊是否增加秩 ↔ 兩端點是否已連通。
• 並查集完美解決動態連通性判定。