395. 冗余路径

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

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

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

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

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

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

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

输入格式

第 1 行输入 F 和 R。

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

输出格式

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

数据范围

1≤F≤5000,
F−1≤R≤10000

输入样例：

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

输出样例：

2

思路：

/* 无向图 双连通分量 1 边的双连通分量 e-dcc 极大的不包含桥的连通块 2 点的双连通分量 v-dcc 极大的不包含割点的连通块 删除后不连通 的 两个定义 桥 o-o 桥o-o | | ↓ | | o-o - o-o 1 如何找桥？ x / y x和y之间是桥 <=> dfn[x] < low[y] y无论如何往上走不到x +y能到的最高的点low[y] = dfn[y] 2 如何找所有边的双连通分量？ 2.1 将所有桥删掉 2.2 stack dfn[x] == low[x] <=> x无论如何走不到x的上面 <=> 从x开始的子树可以用一个栈存 每个割点至少属于两个连通分量 树里的每条边都是桥(割边) 每一个点为边双连通分量 每一条边及两端的点为点双连通分量 o / \ o o /\ /\ o o o o 1 边双连通分量 tarjan回顾 dfn[x] dfs序时间戳 low[x] x能达到的时间戳最小的点 无向图不存在横插边 o / \ o o / / \ y ← x o → x能往左的话 由于无向边 所以y也能往右, 那么在之前dfs的时候就把x先于x的父节点加进来了 */
/* 新建一条道路 使得每两个草场之间都有一个分离的路径 给定一个无向连通图，问最少加几条边，可以将其变为一个边双连通分量 结论：一个边的双连通分量 <=> 任何两个点之间至少存在两个不相交路径 充分性: 对于每两个点都有互相分离的路径的话，则必然为强连通分量 反证 假设有桥(非双连通) x,y必然经过中间的桥 则只x→y的路径必在桥上相交 o-x 桥y-o | | ↓ | | o-o - o-o 必要性：图是一个边双连通分量 <=> 不包含桥 则一定对任意两点x,y x,y之间至少存在两条互相分离(不相交)的路径 反证:假设存在两条相交路径 那么x→y中间必然有桥 // o-o-o-o-o 蓝色路径 (从x出发到y经过边数最少的路径) // - - - - 绿色路径 // x y 对双连通分量做完缩点后 只剩桥和点 o / \ o o /\ /\ o o o o / \ o o o / \ o o /\ /\ o o-o o / \ | | o o__| | |_________| 可以发现对左右两个叶子节点连通后，根节点连向左右叶子节点的边就可以删去了 同理 再把第2个和第4个叶子节点连通后，根节点连向第2个和第4个叶子节点的边也可以删去 第3个叶子节点随便连 给叶子节点按对称性加上边后就没有桥 <=> 变成边的双连通分量 这里cnt= 5 加了ans=(cnt+1)/2=3条 ans >= 下界[cnt/2]取整 == [(cnt+1)/2]取整 其中 cnt为缩完点后度数==1的点的个数 */

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 5010, M = 20010;

int n, m;
int h[N], ne[M], e[M], idx;
/* 无向图是联通的，我从一个点出发就能遍历整个图了，就按照遍历的先后顺序给定的timestamp就行了，也就是dfn值和遍历的先后顺序是绑定，所以走到dfn值不为零的地方就一定是后向边，走进去判断就完事了，当然反边的话就没什么好判断的。 */
int stk[N], top;
int dfn[N], low[N], timestamp;
int id[N], dcc_cnt;
bool is_bridge[N];
int d[N];

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 != -1; 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_bridge[i] = is_bridge[i ^ 1] = true;
            // 添加的时候一起的 所以异或1就可以得到反向边
        }
        else if (i != (from ^ 1)) // 判断反向边
            low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u])
    {
    
        int y;
        dcc_cnt++;
        do
        {
    
            y = stk[top--];
            id[y] = dcc_cnt;
        } while (y != u);
    }
}

int main()
{
    
    scanf("%d %d", &n, &m);
    memset(h, -1, sizeof(h));
    for (int i = 0; i < m; i++)
    {
    
        int a, b;
        scanf("%d %d", &a, &b);
        add(a, b), add(b, a);
    }

    tarjan(1, -1);

    for (int i = 0; i < 2 * m; i++)  // 算边连通分量的度数
    {
    
        if (is_bridge[i])
            d[id[e[i]]]++;
    }

    int cnt = 0;
    for (int i = 1; i <= dcc_cnt; i++)
    {
    
        if (d[i] == 1)
            cnt++;
    }

    printf("%d\n", (cnt + 1) / 2);

    return 0;
}