冗余路径

tarjan桥 模板题 T3

为了从 $F$ 个草场中的一个走到另一个，奶牛们有时不得不路过一些她们讨厌的可怕的树。

奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择。

每对草场之间已经有至少一条路径。

给出所有 $R$ 条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量，路径由若干道路首尾相连而成。

两条路径相互分离，是指两条路径没有一条重合的道路。

但是，两条分离的路径上可以有一些相同的草场。

对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路。

输入格式

第 $1$ 行输入 $F$ 和 $R$。

接下来 $R$ 行，每行输入两个整数，表示两个草场，它们之间有一条道路。

输出格式

输出一个整数，表示最少的需要新建的道路数。

数据范围

$1\le F\le 5000$,
$F-1\le R\le 10000$

输入样例：

7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7

输出样例：

2

思路

边全连通分量的定义：在任意两个点之间都存在至少两条互不相交的路径。

如果从一个点到另一个点有两条相互分离的路径, 删除其中一条路径后仍然连通, 那么就构成了一个边全连通分量。

给一个无向图, 求需要加几条边使其整个图构成边全连通分量。

当一条边被删去后, 两个部分就不连通, 这种边叫做桥。而若在桥的两端再加一条边, 就会形成边全连通分量。因此可以做一遍tarjan求边全连通分量, 统计桥的数量, 也就是全连通分量的数量-1。

无向图求边全连通分量的流程为：

1. 定义 $dfn[N],low[N],timestamp$, 当前分量的点$stk[N]$ , 每个点所在的连通分量$id[N]$
2. 因为边是无向边, 得避免回搜, tarjan需要加一个 $from$ 参数记录上一条边的 $idx$, 无向边的编号是 01, 23, 一对, 故对应的反向边就是 当前边 i ^ 1
3. 和强连通分量类似, 新搜的点先初始化dfn并加入stk
4. 遍历下一个点, 若没搜过就递归搜索, 回溯时更新 low
   1. 若 $dfn[u]<low[j]$ 说明 $j$ 节点无法通过其他路径回到 $u$ 节点, 这条 $u\to j$ 的边是桥
5. 如果更新过就再判断是否为反向边, 不是则更新 $low[u]=min(dfn[j])$
6. 最后若当前节点是连通分量头节点 $dfn[u]==low[u]$, 将stk中存储的点都加入到连通分量中

求完连通分量后, 会变成一个树图： 可以发现, 当把度为0且父节点不同的点相连, 总能找到一个连接方案, 使得删去任意一个树边后仍会连通, 而最小连边数量就是度为0的点数量$cnt$, 除以二向上取整, 即 $\frac{cnt+1}{2}$ 。

枚举所有边, 若当前边是桥, 就把两个端点所在连通分量的度+1。 设度为0的分量个数 $cnt$ , 结果就是 $\frac{cnt+1}{2}$。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 5e3 + 10, M = 2e5 + 10;
int h[N],e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
int id[N], dcc_cnt;
bool is_brige[M];
int d[N];
int n,m;
 
void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;}
 
void tarjan(int u, int from)
{
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u;
    
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j  = e[i];
        if(!dfn[j])
        {
            tarjan(j, i);
            low[u] = min(low[u], low[j]);
            if(dfn[u] < low[j])
                is_brige[i] = is_brige[i ^ 1] = true;
        }
        else if(i != (from ^ 1)) low[u] = min(low[u], dfn[j]);
    }
    
    if(dfn[u] == low[u])
    {
        ++ dcc_cnt;
        int y;
        do {
            y = stk[top--];
            id[y] = dcc_cnt;
        }while(y != u);
    }
}
 
int main()
{
    memset(h , -1, sizeof h);
    cin >> n >> m;
    while(m--)
    {
        int a, b;
        cin >> a >> b;
        add(a,b), add(b,a);
    }
    
    tarjan(1, -1);
    
    for(int i = 0; i < idx; i ++)
    {
        if(is_brige[i])
            d[id[e[i]]]++;
    }
    
    int cnt = 0;
    for(int i = 1; i <= dcc_cnt; i++)
        if(d[i] == 1)
            cnt++;
    cout << (cnt + 1) / 2 << endl;
    
    return 0;
}