跳转至

边双连通分量

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

桥

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

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

边双连通分量

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

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

我们可以在 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)\) 求出。

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#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;
}