当前位置：首页 > news >正文

题解：AcWing 395 冗余路径

news 2026/6/18 7:53:56

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AcWing：395. 冗余路径 - AcWing题库

【题目描述】

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

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

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

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

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

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

可能有不止一条道路直接连接同一对草场，尽管如此，你仍可以在它们之间再建一条道路，作为另一条不同的道路。

【输入】

第1 11行输入F FF和R RR。

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

【输出】

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

【输入样例】

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

【输出样例】

【核心思想】

问题分析：给定无向连通图，要求添加最少的新边，使得任意两点之间至少有两条边不相交的路径。这等价于使图变为边双连通图（不存在桥）。关键在于理解：桥是限制边双连通性的唯一障碍，只要消除所有桥，图就变为边双连通。
算法选择：
- Tarjan算法求桥：使用l o w lowlow数组和d f n dfndfn数组找出所有桥边
- 边双连通分量分解：将图分解为若干个边双连通分量（去掉桥后的连通块）
- 缩点建树：将每个边双连通分量缩成一个点，桥作为边，构建一棵树
- 叶子节点配对：统计缩点树中的叶子节点数，答案为( l e a f + 1 ) / 2 (leaf + 1) / 2(leaf+1)/2
关键步骤：
- Step 1 - Tarjan求桥：
  - DFS遍历图，维护d f n [ x ] dfn[x]dfn[x]（时间戳）和l o w [ x ] low[x]low[x]（能通过回边到达的最小时间戳）
  - 对于边( x , y ) (x, y)(x,y)，若l o w [ y ] > d f n [ x ] low[y] > dfn[x]low[y]>dfn[x]，则该边是桥
  - 使用异或技巧i ^ 1处理双向边，避免重复访问
- Step 2 - 边双连通分量分解：
  - 使用栈记录当前DFS路径上的节点
  - 当d f n [ x ] = l o w [ x ] dfn[x] = low[x]dfn[x]=low[x]时，找到边双连通分量的根
  - 弹出栈中节点直到x xx，这些节点构成一个边双连通分量
- Step 3 - 缩点建树：
  - 每个边双连通分量缩成一个点
  - 桥边连接不同的分量，形成一棵树
- Step 4 - 统计叶子节点：
  - 遍历所有桥边，统计每个分量在缩点树中的度数
  - 度数为1的分量是叶子节点
- Step 5 - 计算答案：
  - 设叶子节点数为c n t cntcnt
  - 答案为( c n t + 1 ) / 2 (cnt + 1) / 2(cnt+1)/2，即把叶子两两配对需要的边数
时间/空间复杂度：
- 时间复杂度：O ( F + R ) O(F + R)O(F+R)，Tarjan算法和后续处理均为线性时间
- 空间复杂度：O ( F + R ) O(F + R)O(F+R)，存储图和各种辅助数组
边双连通分量与桥的核心思想：
- 桥的定义：删除后会使图不连通的边，是边双连通性的瓶颈
- 边双连通分量：不含桥的最大连通子图，分量内任意两点有两条边不相交路径
- 缩点树的性质：将边双连通分量缩点后，桥形成一棵树，叶子节点代表"边缘"分量
- 最优加边策略：在缩点树中，连接两个叶子节点可以同时减少两个叶子的度数
- 答案公式：( l e a f + 1 ) / 2 (leaf + 1) / 2(leaf+1)/2表示将l e a f leafleaf个叶子两两配对（向上取整）
- 适用于网络可靠性分析、关键路径识别、图加固优化类问题

【算法标签】

#双连通分量

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;// ================= 常量与全局变量 =================constintN=5000;// 最大节点数constintM=20005;// 最大边数（注意双向边，所以是两倍）intn,m;// n: 节点数, m: 边数// ---------- 邻接表相关 ----------inth[N];// 邻接表头结点inte[M];// 存储边的终点intne[M];// 存储下一条边的索引intidx;// 边的编号计数器（从0开始）// ---------- Tarjan 相关 ----------intdfn[N];// 时间戳：节点首次被访问的顺序intlow[N];// 能通过回边到达的最小时间戳inttot;// 时间戳计数器stack<int>stk;// 栈，用于存储当前正在处理的节点// ---------- 桥与边双连通分量相关 ----------intbri[M];// 标记边是否为桥（1表示是桥）intcon_cnt;// 边双连通分量的总数intcon_id[N];// 每个节点所属的边双连通分量编号intcon_size[N];// 每个边双连通分量的大小intd[N];// 每个边双连通分量的度数（在缩点树中的度数）vector<int>ans[N];// 存储每个边双连通分量包含的节点// ================= 添加边 =================voidadd(inta,intb){e[idx]=b;// 存储边的终点ne[idx]=h[a];// 头插法h[a]=idx++;// 更新头结点}// ================= Tarjan 算法求边双连通分量 =================voidtarjan(intx,intin_edge){dfn[x]=low[x]=++tot;// 初始化时间戳stk.push(x);// 当前节点入栈// 遍历 x 的所有邻接点for(inti=h[x];i!=-1;i=ne[i]){inty=e[i];// 邻接点 yif(!dfn[y])// y 尚未访问{tarjan(y,i);// 递归访问 ylow[x]=min(low[x],low[y]);// 用子树更新 low[x]// 判断边 (x, y) 是否为桥if(low[y]>dfn[x]){// 标记该边和其反向边为桥bri[i]=bri[i^1]=true;}}// 如果是回退边，且不是刚刚过来的那条反向边elseif(i!=(in_edge^1)){low[x]=min(low[x],dfn[y]);// 用回边更新 low[x]}}// 如果 x 是边双连通分量的根节点if(dfn[x]==low[x]){++con_cnt;// 新建一个边双连通分量while(1){inty=stk.top();// 取出栈顶节点stk.pop();// 弹出栈顶con_id[y]=con_cnt;// 记录节点 y 所属的分量编号con_size[con_cnt]++;// 更新分量大小ans[con_cnt].push_back(y);// 将节点加入该分量if(y==x)// 直到弹出 x 为止break;}}}// ================= 主函数 =================intmain(){// 读取节点数和边数cin>>n>>m;// 初始化邻接表头结点为 -1memset(h,-1,sizeof(h));// 读入 m 条无向边while(m--){intu,v;cin>>u>>v;add(u,v);// 添加正向边add(v,u);// 添加反向边}// 从节点 1 开始执行 Tarjan 算法tarjan(1,0);// ========= 统计缩点后每个分量的度数 =========for(inti=0;i<idx;i++){if(bri[i])// 如果该边是桥{d[con_id[e[i]]]++;// 该边终点所在分量的度数加1}}// ========= 统计叶子节点（度数为1的分量） =========intcnt=0;for(inti=1;i<=con_cnt;i++){if(d[i]==1)// 度数为1，即为叶子节点{cnt++;}}// ========= 输出答案 =========// 将叶子节点两两配对，需要的最少边数为 (cnt + 1) / 2cout<<(cnt+1)/2<<endl;return0;}