发布时间：2024-07-31

动态维护边双连通分量

struct DynamicBCC {
    // 成员变量
    vector<int> ecc; // 双连通分量
    vector<int> dsu; // 并查集
    vector<int> siz; // 并查集大小
    vector<int> par;  // 生成树父节点
    vector<int> lcats; // LCA时间戳
    int bridge;     // 当前桥数量
    int ts;        // LCA标记
    int ecc_count; // 双连通分量数量
    int dsu_count; // 并查集数量
    // 初始化（节点数0-based）（实际用的时候为创建n+1的size）
    DynamicBCC(){}
    DynamicBCC(int n) {init(n);}
    


    void init(int n){
        ecc.resize(n);
        dsu.resize(n);
        siz.assign(n, 1);
        iota(ecc.begin(), ecc.end(), 0);
        iota(dsu.begin(), dsu.end(), 0);
        par.assign(n, -1);
        lcats.assign(n, 0);
        bridge = 0;
        ts = 0;
        ecc_count = dsu_count = n - 1;
    }
    int find_ecc(int x){
        if(x==-1)return -1;
        return ecc[x]==x?x:ecc[x]=find_ecc(ecc[x]);
    }
    int find(int x){
        x=find_ecc(x);
        return dsu[x]==x?x:dsu[x]=find(dsu[x]);
    }
    // 辅助方法：重新设置u为树根
    void make_root(int u) {
        int root = u;
        int child = -1;
        while (u != -1) {
            int p = find_ecc(par[u]);
            par[u] = child;
            dsu[u] = root;
            child = u;
            u = p;
        }
        siz[root] = siz[child];
    }
    


    // 合并两个路径（LCA算法）
    void merge_path(int a, int b) {
        ts++;
        vector<int> path_a, path_b;
        int lca = -1;
        // 双向查找LCA
        while (lca == -1) {
            if (a != -1) {
                a = find_ecc(a);
                path_a.push_back(a);
                if (lcats[a] == ts) {
                    lca = a;
                    break;
                }
                lcats[a] = ts;
                a = par[a];
            }
            if (b != -1) {
                b = find_ecc(b);
                path_b.push_back(b);
                if (lcats[b] == ts) {
                    lca = b;
                    break;
                }
                lcats[b] = ts;
                b = par[b];
            }
        }
        set<int> s;
        for (auto v : path_a) {
            s.insert(find_ecc(v));
            ecc[v] = lca;
            if (v == lca) break;
            --bridge;
        }
        for (auto v : path_b) {
            s.insert(find_ecc(v));
            ecc[v] = lca;
            if (v == lca) break;
            --bridge;
        }
        ecc_count -= s.size() -1;
    }
    // 添加边并动态维护桥的数量
    void addEdge(int u, int v) {
        u = find_ecc(u);
        v = find_ecc(v);
        if (u == v) return;

        int fu = find(u);
        int fv = find(v);

        if (fu != fv) { // 不同连通块
            bridge++;
            if (siz[fu] > siz[fv])swap(u, v), swap(fu, fv);
            make_root(u);
            par[u] = dsu[u] = v;
            siz[fv] += siz[u];
            dsu_count--;
        } else { // 同一连通块，合并环
            merge_path(u, v);
        }
    }
    
    // 获取当前桥的总数
    int bridge_count() const { return bridge; }
    int count() const { return ecc_count; }
    int comb_count() const { return dsu_count; }
} ecc;