边双连通分量

对于一个无向连通图，若删去其中任意一条边，都不会改变图的连通性，则称这个图边双连通。

桥

对于一个无向图，若删去一条边之后，图的连通性发生了变化（连通块数量变多），则称这条边为图的一个桥。

桥可以使用 Tarjan 算法求出。考虑 dfs 生成树，返祖边一定不是桥；对于树边 \((u,v)\)（\(u\) 是 \(v\) 的父亲），若 low[v] >= dfn[v]，那么这条边就是桥。

边双连通分量

一个无向图的极大边双连通子图称为边双连通分量。

性质

边双之间两两无交；
每个点唯一属于一个边双；
对于同一个边双内的任意两点 \(x,y\)，都能找到两条不包含公共边的 \(x\to y\) 的简单路径（不经过重复边，点可以重复走，下同）；
对于同一个边双内的任意三个点 \(x,y,z\)，都能找到 \(x\to y\to z\) 的简单路径；
对于同一个边双内的任意四个点 \(x,y,a,b\)，要么能找到两条不包含公共边的 \(x\to a,y\to b\) 的简单路径，要么能找到两条不包含公共边的 \(x\to b,y\to a\) 的简单路径。

在无向图中，每个点恰好属于一个边双分量；各个边双分量之间被桥隔开，形成一棵树形结构。

我们可以在 Tarjan 中维护一个栈来求解边双，亦可以先标记出所有桥，然后用第二次 dfs 求出边双。

例题 1

给定一个 \(n\) 个点 \(m\) 条边的无向图，保证图连通。找到两个点 \(s,t\)，使得 \(s\) 到 \(t\) 必须经过的边最多（一条边无论走哪条路线都经过ta，这条边就是必须经过的边）

注意到这些边一定是桥，否则一定不是。因此求出边双，然后就是求树上最长链。

P4214 [CERC2015] Juice Junctions

给定一个无向图，保证每个节点的度数不超过 \(3\)。请你求出每对 \((a,b),a<b\) 分别为网络流的源汇点时，最小割之和。

\(n\le 3000,\ m\le 4500\)

注意到由于每个点的度数不超过 \(3\)，因此每个点对的答案也不会超过 \(3\)。当两个点不在同一个连通块时，答案为 \(0\)；当两个点不在同一个边双内时，答案为 \(1\)；现在考虑如何区分答案为 \(2\) 和 \(3\) 的情况。

答案为 \(3\) 当且仅当两点之间存在 \(3\) 条没有重复边的路径，因此删掉图上任意一条边之后，两个点仍在同一个边双内；其余情况答案为 \(2\)。我们可以枚举删掉每一条边，然后跑 Tarjan 求出边双，现在问题转化为快速判断两个点是否始终在一个边双内。注意到这个问题等价于判断两个序列是否相等，这里可以使用哈希 \(O(1)\) 求出。

代码

#include<iostream>
#define ull unsigned long long
using namespace std;
const int N = 3010;
const int M = 4510;
const int BASE = 3001;

struct Edge {
    int v, next;
} pool[2 * M];
int ne = 1, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

int n, m;

int ban[2 * M];

int dfn[N], low[N], dt;
int col[N], bccCnt;
int sz[N];

int sta[N], top;

void tarjan(int u, int fe) {
    low[u] = dfn[u] = ++dt;
    sta[++top] = u;
    for(int e = head[u]; e; e = pool[e].next) {
        if(e == fe || ban[e]) continue;
        int v = pool[e].v;
        if(!dfn[v]) {
            tarjan(v, e ^ 1);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[v]) {
                col[v] = ++bccCnt;
                ++sz[bccCnt];
                while(sta[top] != v) {
                    col[sta[top]] = bccCnt;
                    ++sz[bccCnt];
                    --top;
                }
                --top;
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(!fe && top) {
        col[u] = ++bccCnt;
        ++sz[bccCnt];
        while(sta[top] != u) {
            col[sta[top]] = bccCnt;
            ++sz[bccCnt];
            --top;
        }
        --top;
    }
}

void clear() {
    for(int i = 1; i <= n; i++) dfn[i] = low[i] = col[i] = sz[i] = 0;
    bccCnt = dt = 0;
}

void get_col() {
    for(int i = 1; i <= n; i++) {
        if(!dfn[i]) tarjan(i, 0);
    }
}

int precol[N], hsh[N];
int ans;

int main() {

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }

    for(int i = 1, pre = 0; i <= n; i++) {
        if(!dfn[i]) {
            tarjan(i, 0);
            int sum = 0;
            for(int j = pre + 1; j <= bccCnt; j++) {
                ans += sum * sz[j];
                sum += sz[j];
            }
            pre = bccCnt;
        }
    }

    for(int i = 1; i <= n; i++) precol[i] = col[i];

    for(int e = 2; e <= ne; e += 2) {
        ban[e] = ban[e ^ 1] = 1;
        clear();
        get_col();
        for(int i = 1; i <= n; i++) hsh[i] = hsh[i] * BASE + col[i];
        ban[e] = ban[e ^ 1] = 0;
    }

    for(int i = 1; i <= n; i++) {
        for(int j = i + 1; j <= n; j++) {
            if(precol[i] != precol[j]) continue;
            if(hsh[i] == hsh[j]) ans += 3;
            else ans += 2;
        }
    }

    cout << ans << endl;

    return 0;
}