graph/connected-components/incremental-bridge-connectivity.hpp

• View this file on GitHub
• Last update: 2024-10-01 21:25:01+02:00
• Include: #include "graph/connected-components/incremental-bridge-connectivity.hpp"
• Link: https://scrapbox.io/data-structures/Incremental_Bridge-Connectivity

Depends on

• structure/union-find/union-find.hpp

Verified with

• test/yosupo-two-edge-connected-components-2.test.cpp

Code

/*
在线维护边双联通分量
https://scrapbox.io/data-structures/Incremental_Bridge-Connectivity
*/
#pragma once
#include "../../structure/union-find/union-find.hpp"

struct IncrementalBridgeConnectivity {
   public:
    IncrementalBridgeConnectivity() = default;
    explicit IncrementalBridgeConnectivity(int sz) : cc(sz), bcc(sz), fa(sz, sz), bridge(0) {}
    int find(int x) {
        return bcc.find(x);
    }
    size_t bridge_size() const {
        return bridge;
    }

    void add_edge(int x, int y) {
        x = bcc.find(x), y = bcc.find(y);
        if (cc.find(x) == cc.find(y)) {
            int w = lca(x, y);
            compress(x, w);
            compress(y, w);
        } else {
            // 不在同一个强联通分量当中
            if (cc.size(x) > cc.size(y)) swap(x, y);
            link(x, y);
            cc.unite(x, y);
            bridge++;
        }
    }

   private:
    UnionFind cc, bcc;  // cc 是否现在在同一个强联通分量中，bcc 是否在同一个边双联通分量重
    vector<int> fa;     // 根据边双联通分量缩点后 fa[i] i 点的父亲，如果 fa[i] = sz 则 i 没有父亲
    size_t bridge;      // 桥的个数

    int size() {
        return fa.size();
    }

    int par(int x) {
        if (fa[x] == size()) return size();  // 没有父亲
        return bcc.find(fa[x]);
    }

    int lca(int x, int y) {
        // 相当于 x 往上走一步，y 往上走一步，记录路径经过的点，第一个被经过 2 次的点就是 lca
        unordered_set<int> vis;
        while (true) {
            if (x != size()) {                        // 判断 x 是否是无效点
                if (!vis.insert(x).second) return x;  // second 返回一个 bool 值，表示是否插入成功，如果没成功，说明之前已经插入这个点
                x = par(x);
            }
            swap(x, y);
        }
    }

    void compress(int x, int y) {
        while (bcc.find(x) != bcc.find(y)) {
            int nxt = par(x);
            fa[x] = fa[y];
            bcc.unite(x, y);
            x = nxt;
            bridge--;
        }
    }

    void link(int x, int y) {
        int v = x, pre = y;
        while (v != size()) {
            int nxt = par(v);
            fa[v] = pre;
            pre = v;
            v = nxt;
        }
    }
};

#line 1 "graph/connected-components/incremental-bridge-connectivity.hpp"
/*
在线维护边双联通分量
https://scrapbox.io/data-structures/Incremental_Bridge-Connectivity
*/
#line 2 "structure/union-find/union-find.hpp"
#include <bits/stdc++.h>

using namespace std;

struct UnionFind {
    vector<int> data;
    vector<int> f;

    UnionFind() = default;

    explicit UnionFind(size_t sz) : data(sz, 1), f(sz) {
        iota(f.begin(), f.end(), 0);
    }

    bool unite(int x, int y) {  // x merge to y
        x = find(x), y = find(y);
        if (x == y) return false;
        data[y] += data[x];
        f[x] = y;
        return true;
    }
    int find(int x) {
        if (f[x] == x) return x;
        int y = find(f[x]);
        data[y] += data[x];
        f[x] = y;
        return f[x];
    }
    int size(int x) {
        return data[find(x)];
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    vector<vector<int>> groups() {
        int n = (int)data.size();
        vector<vector<int>> ans(n);
        for (int i = 0; i < n; i++) {
            ans[find(i)].push_back(i);
        }

        ans.erase(remove_if(ans.begin(), ans.end(), [&](const vector<int>& v) {
                      return v.empty();
                  }),
                  ans.end());
        return ans;
    }
};
#line 7 "graph/connected-components/incremental-bridge-connectivity.hpp"

struct IncrementalBridgeConnectivity {
   public:
    IncrementalBridgeConnectivity() = default;
    explicit IncrementalBridgeConnectivity(int sz) : cc(sz), bcc(sz), fa(sz, sz), bridge(0) {}
    int find(int x) {
        return bcc.find(x);
    }
    size_t bridge_size() const {
        return bridge;
    }

    void add_edge(int x, int y) {
        x = bcc.find(x), y = bcc.find(y);
        if (cc.find(x) == cc.find(y)) {
            int w = lca(x, y);
            compress(x, w);
            compress(y, w);
        } else {
            // 不在同一个强联通分量当中
            if (cc.size(x) > cc.size(y)) swap(x, y);
            link(x, y);
            cc.unite(x, y);
            bridge++;
        }
    }

   private:
    UnionFind cc, bcc;  // cc 是否现在在同一个强联通分量中，bcc 是否在同一个边双联通分量重
    vector<int> fa;     // 根据边双联通分量缩点后 fa[i] i 点的父亲，如果 fa[i] = sz 则 i 没有父亲
    size_t bridge;      // 桥的个数

    int size() {
        return fa.size();
    }

    int par(int x) {
        if (fa[x] == size()) return size();  // 没有父亲
        return bcc.find(fa[x]);
    }

    int lca(int x, int y) {
        // 相当于 x 往上走一步，y 往上走一步，记录路径经过的点，第一个被经过 2 次的点就是 lca
        unordered_set<int> vis;
        while (true) {
            if (x != size()) {                        // 判断 x 是否是无效点
                if (!vis.insert(x).second) return x;  // second 返回一个 bool 值，表示是否插入成功，如果没成功，说明之前已经插入这个点
                x = par(x);
            }
            swap(x, y);
        }
    }

    void compress(int x, int y) {
        while (bcc.find(x) != bcc.find(y)) {
            int nxt = par(x);
            fa[x] = fa[y];
            bcc.unite(x, y);
            x = nxt;
            bridge--;
        }
    }

    void link(int x, int y) {
        int v = x, pre = y;
        while (v != size()) {
            int nxt = par(v);
            fa[v] = pre;
            pre = v;
            v = nxt;
        }
    }
};

Back to top page