本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing395. 冗余路径 - 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【输出样例】2【核心思想】问题分析给定无向连通图要求添加最少的新边使得任意两点之间至少有两条边不相交的路径。这等价于使图变为边双连通图不存在桥。关键在于理解桥是限制边双连通性的唯一障碍只要消除所有桥图就变为边双连通。算法选择Tarjan算法求桥使用l o w lowlow数组和d f n dfndfn数组找出所有桥边边双连通分量分解将图分解为若干个边双连通分量去掉桥后的连通块缩点建树将每个边双连通分量缩成一个点桥作为边构建一棵树叶子节点配对统计缩点树中的叶子节点数答案为( l e a f 1 ) / 2 (leaf 1) / 2(leaf1)/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(cnt1)/2即把叶子两两配对需要的边数时间/空间复杂度时间复杂度O ( F R ) O(F R)O(FR)Tarjan算法和后续处理均为线性时间空间复杂度O ( F R ) O(F R)O(FR)存储图和各种辅助数组边双连通分量与桥的核心思想桥的定义删除后会使图不连通的边是边双连通性的瓶颈边双连通分量不含桥的最大连通子图分量内任意两点有两条边不相交路径缩点树的性质将边双连通分量缩点后桥形成一棵树叶子节点代表边缘分量最优加边策略在缩点树中连接两个叶子节点可以同时减少两个叶子的度数答案公式( l e a f 1 ) / 2 (leaf 1) / 2(leaf1)/2表示将l e a f leafleaf个叶子两两配对向上取整适用于网络可靠性分析、关键路径识别、图加固优化类问题【算法标签】#双连通分量【代码详解】#includebits/stdc.husingnamespacestd;// 常量与全局变量 constintN5000;// 最大节点数constintM20005;// 最大边数注意双向边所以是两倍intn,m;// n: 节点数, m: 边数// ---------- 邻接表相关 ----------inth[N];// 邻接表头结点inte[M];// 存储边的终点intne[M];// 存储下一条边的索引intidx;// 边的编号计数器从0开始// ---------- Tarjan 相关 ----------intdfn[N];// 时间戳节点首次被访问的顺序intlow[N];// 能通过回边到达的最小时间戳inttot;// 时间戳计数器stackintstk;// 栈用于存储当前正在处理的节点// ---------- 桥与边双连通分量相关 ----------intbri[M];// 标记边是否为桥1表示是桥intcon_cnt;// 边双连通分量的总数intcon_id[N];// 每个节点所属的边双连通分量编号intcon_size[N];// 每个边双连通分量的大小intd[N];// 每个边双连通分量的度数在缩点树中的度数vectorintans[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(intih[x];i!-1;ine[i]){intye[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){intystk.top();// 取出栈顶节点stk.pop();// 弹出栈顶con_id[y]con_cnt;// 记录节点 y 所属的分量编号con_size[con_cnt];// 更新分量大小ans[con_cnt].push_back(y);// 将节点加入该分量if(yx)// 直到弹出 x 为止break;}}}// 主函数 intmain(){// 读取节点数和边数cinnm;// 初始化邻接表头结点为 -1memset(h,-1,sizeof(h));// 读入 m 条无向边while(m--){intu,v;cinuv;add(u,v);// 添加正向边add(v,u);// 添加反向边}// 从节点 1 开始执行 Tarjan 算法tarjan(1,0);// 统计缩点后每个分量的度数 for(inti0;iidx;i){if(bri[i])// 如果该边是桥{d[con_id[e[i]]];// 该边终点所在分量的度数加1}}// 统计叶子节点度数为1的分量 intcnt0;for(inti1;icon_cnt;i){if(d[i]1)// 度数为1即为叶子节点{cnt;}}// 输出答案 // 将叶子节点两两配对需要的最少边数为 (cnt 1) / 2cout(cnt1)/2endl;return0;}【运行结果】7 7 1 2 2 3 3 4 2 5 4 5 5 6 5 7 2
