python/TangDou/AcWing/DCC/395.md

AcWing 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的结点的个数，即叶结点的个数，记为 leaf ，则要使树中任意两个节点之间都有两条独立的路径，则需要添加的边数为\large ⌊\frac {leaf+1}{2}⌋

可以用下面的栗子来解释一下：

• 当叶子节点的个数leaf为偶数时：

• 当叶子节点的个数leaf为奇数时：

综上，结合\dfrac {leaf}{2} 和\dfrac {leaf+1}{2} 答案就是\dfrac {leaf+1}{2} 向下取整

算法设计

• ① 先把原图建立出来
• ② tarjan求割边，同时求出边连通分量，缩点
• ③ 遍历每一条边，找到割边，设这条割边的两个端点为x , y，节点x所在的边连通分量为a=id[x]，节点y所在的边连通分量为b=id[y]，分别统计a,b的度
• ④ 遍历这e\_dcc个边连通分量，其实也就是缩完之后的e\_dcc个点，统计入度为1的顶点个数，最终答案就是\dfrac {leaf+1}{2} 向下取整

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 5010, M = 20010;

int n, m;
int d[N]; // 边双连通分量块的度

// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

// 边双连通分量
int dfn[N], low[N], ts, stk[N], top, root;
vector<int> bcc[N]; // 边双中有哪些原始点,集合-> 点
int id[N], bcnt;    // 原始点x属于哪个边双连通分量，bcnt指边双连通分量个数,点->集合
int is_bridge[M];   // 哪些边是割边

void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++ts;
    stk[++top] = u;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (!dfn[v]) {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if (dfn[u] < low[v]) is_bridge[i] = is_bridge[i ^ 1] = 1; // 记录割边
        } else if (i != (fa ^ 1))
            low[u] = min(low[u], dfn[v]);
    }

    if (dfn[u] == low[u]) {
        ++bcnt; // 边双号
        int x;
        do {
            x = stk[top--];
            id[x] = bcnt;           // 记录点与边双关系
            bcc[bcnt].push_back(x); // 记录边双中有哪些点
        } while (x != u);
    }
}

int main() {
    memset(h, -1, sizeof h);
    scanf("%d %d", &n, &m);
    while (m--) {
        int a, b;
        scanf("%d %d", &a, &b);
        if (a != b) add(a, b), add(b, a);
    }
    // Tarjan算法缩点，生成边双连通分量, 缩点后，新图中的边将只是割边。
    // 注意：这里并没有真的创建新图，而是心中有图而手中无图。
    // 获取边双连通分量的过程中，记录了哪些边是割边，下面将利用割边解决问题
    for (root = 1; root <= n; root++)
        if (!dfn[root]) tarjan(root, -1);

    // 下面统计新图中每个点的度,这是一个经典用法，需要理解和记忆
    // 计算新图中度为1的点(边双连通分量)的个数，也就是叶子节点的个数
    for (int u = 1; u <= n; u++)            // ①枚举每个原始点
        for (int i = h[u]; ~i; i = ne[i]) { // ②枚举此点的每条出边
            // (1) 由于每个节点都可以从1~n枚举到，所以u->v,v->u也都可以被枚举到
            // (2) 由于割边是成对出现，而成对的割边都可以通过出边的方式被枚举到，也就是成对的割边
            // 为两个节点都提供了一个度，这个度可以理解为在无向图中某个点的连接边数，
            // 这个边数可不是a->b,b->a这样的形式，只是a-b
            int v = e[i];
            // 如果某条边是割边，说明它在新图中是存在的边
            if (is_bridge[i]) d[id[v]]++; // 如果此边是割边,则新点的度++
        }

    // 度为1的是叶子
    int cnt = 0;
    for (int i = 1; i <= bcnt; i++) // 注意：模板中的bcnt是从1开始的
        if (d[i] == 1) cnt++;       // 多少个度为1的节点(边双连通分量)

    // 贪心,叶子结点的除以2上取整即是答案
    printf("%d\n", (cnt + 1) / 2);
    return 0;
}