桥，边双连通分量

桥

在无向图上，如果去掉某条边之后，图的连通性受到破坏(分解成多个部分)，那么称这条边叫做图的桥(割边)。

求割边的算法和求割点的算法较为相近。只需要将

\[ low[v] \ge pre[u] \]

改为

\[ low[v] > pre[u] \]

满足这个条件时，\(v\) 通过它下面的分支只能达到 \(u\) 下面的节点（而不能到达 \(u\)）。这样，如果去掉 \(u\rightarrow v\) 的边，而 \(v\) 又不能通过别的途径走到 \(u\)，于是图分成了两部分。根据定义，\(u\rightarrow v\) 的边就是图的桥。

例题

U119054 【模板】割边/边双连通分量

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5E5 + 10;
const int M = 1E6 + 10;

int nn;
struct Edge{
    int v;
    int next;
} pool[M];
int head[N];

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

int n, m;
int w[N];

// 求桥
int dt;
int pre[N], low[N];
bool bridge[M];
void tarjan(int u, int f){
    low[u] = pre[u] = ++dt;
    for(int i = head[u]; i != -1; i = pool[i].next){
        int v = pool[i].v;
        if(!pre[v]){
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] > pre[u]){
                // 双向边正反都是桥
                // 如果需要这种写法，应使用链式前向星存图，并且需要把head初始化为-1，pool要从0开始存边
                bridge[i] = 1;
                bridge[i ^ 1] = 1;
            }
        } else if(v != f){
            low[u] = min(low[u], pre[v]);
        }
    }
}

// 这些是求边双的代码，可以先不看
int bccCnt;
int bccNum[N], ans[N];
void dfs(int u){
    bccNum[u] = bccCnt;
    ans[bccCnt] ^= w[u];
    for(int i = head[u]; i != -1; i = pool[i].next){
        if(bridge[i]) continue;
        int v = pool[i].v;
        if(!bccNum[v]){
            dfs(v);
        }
    }
}

int main(){

    memset(head, -1, sizeof(head));
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> w[i];
    }
    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }

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

    for(int i = 1; i <= n; i++){
        if(!bccNum[i]){
            ++bccCnt;
            dfs(i);
        }
    }

    sort(ans + 1, ans + 1 + bccCnt);

    for(int i = 1; i <= bccCnt; i++){
        cout << ans[i] << '\n';
    }
    cout << endl;

    return 0;
}

边双连通分量

对于一个无向图，若其上的任意两个点 \(u\) 和 \(v\) 之间存在两条路径，它们不存在公共的边，则称这两个点边双连通。

注意，无向图中边双连通的两个点，其之间的两条路径可能存在重合的点，这时它们并不点双连通，但满足边双连通的要求。

边双连通分量由两种求法：

找出所有桥，标记它们，再对图进行 dfs，不走桥，那 dfs 出的每一个连通块就是一个边双；
在 tarjan 内部，仿照点双和 SCC 的求法，使用栈；

对于栈的求法，需要注意在 dfs 结束后

U119054 【模板】割边/边双连通分量就使用了第一种方法，需要写两个函数，但是逻辑简单

若使用第二种方法，也需要仿照点双连通分量，在函数的结尾进行特殊处理。因为在函数调用结束后，栈内可能还有剩余的节点，它们是以根节点 \(u\) 为根的边双分量。因此需要在 dfs 结束时将栈内剩余的元素处理掉。

例题

U119054 【模板】割边/边双连通分量

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5E5 + 10;
const int M = 1E6 + 10;

int nn;
struct Edge{
    int v;
    int next;
} pool[M];
int head[N];

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

int n, m;
int w[N];

int dt;
int pre[N], low[N];
bool bridge[M];
void tarjan(int u, int f){
    low[u] = pre[u] = ++dt;
    for(int i = head[u]; i != -1; i = pool[i].next){
        int v = pool[i].v;
        if(!pre[v]){
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] > pre[u]){
                bridge[i] = 1;
                bridge[i ^ 1] = 1;
            }
        } else if(v != f){
            low[u] = min(low[u], pre[v]);
        }
    }
}

int bccCnt;
int bccNum[N], ans[N];
void dfs(int u){
    bccNum[u] = bccCnt;
    ans[bccCnt] ^= w[u];
    for(int i = head[u]; i != -1; i = pool[i].next){
        if(bridge[i]) continue;
        int v = pool[i].v;
        if(!bccNum[v]){
            dfs(v);
        }
    }
}

int main(){

    memset(head, -1, sizeof(head));
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> w[i];
    }
    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }

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

    for(int i = 1; i <= n; i++){
        if(!bccNum[i]){
            ++bccCnt;
            dfs(i);
        }
    }

    sort(ans + 1, ans + 1 + bccCnt);

    for(int i = 1; i <= bccCnt; i++){
        cout << ans[i] << '\n';
    }
    cout << endl;

    return 0;
}

P2860 [USACO06JAN] Redundant Paths G

使用栈找出边双连通分量，重点是函数中间对重边的处理和结尾的特判

对于重边，即既有 \(A\rightarrow B\)又有\(B\rightarrow A\)，那 \(A\) 、 \(B\) 就可以组成一个边双。但是这样会被 "if(v != f)" 去除。

图：错误的去除真正的回边

为了解决这个问题，可以将 \(Vector\) 改为了链式前向星，再把树边配对的反向边的编号，代替 \(tarjan\) 函数的 \(fa\) 参数，即用边的判断代替点的判断。

对于函数结尾的特判，主要是这种情况：

如图，1234组成了一个边双。但是如果不在根节点进行特殊处理，这个边双就不会被记录。因此，需要在根节点把栈内剩余的所有节点记为同一个边双。

代码

#include<iostream>
#include<stack>
#include<cstring>
#define ll long long
using namespace std;
const ll N = 5005;
const ll M = 1E4 + 10;

int nn;
struct Edge{
    int v;
    int next;
} pool[M];
int head[N];

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

ll n, m;

stack<ll> sta;
ll dt, bccCnt;
ll pre[N], low[N], bccNum[N];
void tarjan(ll u, ll f, ll ed){
    low[u] = pre[u] = ++dt;
    sta.push(u);
    for(int i = head[u]; i != -1; i = pool[i].next){
        int v = pool[i].v;
        if(!pre[v]){
            tarjan(v, u, i ^ 1);
            low[u] = min(low[u], low[v]);
            if(low[v] > pre[u]){
                bccNum[v] = ++bccCnt;
                while(sta.top() != v){
                    bccNum[sta.top()] = bccCnt;
                    sta.pop();
                }
                sta.pop();
            }
        } else if(i != ed){
            low[u] = min(low[u], pre[v]);
        }
    }
    if(u == 1){
        ++bccCnt;
        while(!sta.empty()){
            bccNum[sta.top()] = bccCnt;
            sta.pop();
        }
    }
}

ll degree[N];

int main(){

    memset(head, -1, sizeof(head));

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

    tarjan(1, 0, -1);

    if(bccCnt == 1){
        cout << 0 << endl;
        return 0;
    }

    for(ll u = 1; u <= n; u++){
        for(int j = head[u]; j != -1; j = pool[j].next){
            int v = pool[j].v;
            if(bccNum[u] != bccNum[v]){
                degree[bccNum[u]]++;
                degree[bccNum[v]]++;
            }
        }
    }

    ll ans = 0;
    for(ll i = 1; i <= bccCnt; i++){
        if(degree[i] == 2){
            ans++;
        }
    }

    cout << ((ans + 1) / 2) << endl;

    return 0;
}