本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing396. 矿场搭建 - AcWing题库【题目描述】煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口使得无论哪一个挖煤点坍塌之后其他挖煤点的工人都有一条道路通向救援出口。请写一个程序用来计算至少需要设置几个救援出口以及不同最少救援出口的设置方案总数。【输入】输入文件有若干组数据每组数据的第一行是一个正整数N NN表示工地的隧道数。接下来的N NN行每行是用空格隔开的两个整数S SS和T TTS ≠ T S≠TST表示挖煤点S SS与挖煤点T TT由隧道直接连接。注意每组数据的挖煤点的编号为1 ∼ M a x 1∼Max1∼Max其中M a x MaxMax表示由隧道连接的挖煤点中编号最大的挖煤点的编号可能存在没有被隧道连接的挖煤点。输入数据以0 00结尾。【输出】每组数据输出结果占一行。其中第i ii行以Case i:开始注意大小写Case与i之间有空格i与:之间无空格:之后有空格。其后是用空格隔开的两个正整数第一个正整数表示对于第i ii组输入数据至少需要设置几个救援出口第二个正整数表示对于第i ii组输入数据不同最少救援出口的设置方案总数。输入数据保证答案小于2 64 2^{64}264输出格式参照以下输入输出样例。【输入样例】9 1 3 4 1 3 5 1 2 2 6 1 5 6 3 1 6 3 2 6 1 2 1 3 2 4 2 5 3 6 3 7 0【输出样例】Case 1: 2 4 Case 2: 4 1【核心思想】问题分析给定一个无向图需要在某些节点设置救援出口使得删除任意一个节点挖煤点坍塌后剩余节点都能到达某个救援出口。这等价于求点双连通分量中的割点分布并在每个点双连通分量中合理设置出口。算法选择Tarjan 算法求点双连通分量通过d f n dfndfn和l o w lowlow数组找出图中的所有点双连通分量割点判定利用l o w [ y ] ≥ d f n [ x ] low[y] \geq dfn[x]low[y]≥dfn[x]判断节点x xx是否为割点分类讨论根据每个点双连通分量中割点的数量决定需要设置的出口数量和方案数关键步骤建图读入m mm条边构建无向图邻接表确定最大节点编号n nnTarjan 求点双连通分量对每个未访问的节点作为根节点执行t a r j a n ( r o o t ) tarjan(root)tarjan(root)使用栈维护当前 DFS 路径上的节点当发现l o w [ y ] ≥ d f n [ x ] low[y] \geq dfn[x]low[y]≥dfn[x]时找到一个点双连通分量将栈中节点弹出直到y yy统计每个分量中的割点数量t m p tmptmp情况1t m p 0 tmp 0tmp0无割点若分量大小为1 11孤立点需要设置1 11个出口方案数× 1 \times 1×1若分量大小≥ 2 \geq 2≥2需要设置2 22个出口方案数× C ( s i z e , 2 ) s i z e × ( s i z e − 1 ) 2 \times C(size, 2) \frac{size \times (size-1)}{2}×C(size,2)2size×(size−1)情况2t m p 1 tmp 1tmp1一个割点需要设置1 11个出口在非割点位置方案数× ( s i z e − 1 ) \times (size - 1)×(size−1)情况3t m p ≥ 2 tmp \geq 2tmp≥2多个割点该分量被多个割点保护无需设置出口输出答案最少出口数r e s resres和总方案数n u m numnum时间/空间复杂度时间复杂度O ( n m ) O(n m)O(nm)Tarjan 算法线性遍历所有节点和边空间复杂度O ( n m ) O(n m)O(nm)存储图结构和辅助数组点双连通分量与割点的核心思想点双连通分量图中删除任意一个节点后仍然连通的极大子图割点作用割点是连接不同点双连通分量的桥梁删除割点会将图分割成多个连通块出口设置策略无割点的分量必须内部设置出口且至少2 22个防止出口所在点坍塌有一个割点的分量割点坍塌时分量孤立需在非割点设1 11个出口有多个割点的分量任意点坍塌都能通过其他割点逃出无需设出口孤立点特判单个孤立点只需设置1 11个出口自己就是出口适用于网络可靠性、关键节点识别、冗余设计类问题【算法标签】#双连通分量【代码详解】#includebits/stdc.husingnamespacestd;// 定义无符号长整型别名用于存储方案数typedefunsignedlonglongULL;// 常量与全局变量 constintN1005;// 最大节点数intn;// 当前测试用例的节点数intm;// 当前测试用例的边数vectorinte[N];// 原图邻接表vectorintne[N];// 未使用的邻接表保留原样// ---------- Tarjan 相关 ----------intdfn[N];// 时间戳节点首次被访问的顺序intlow[N];// 能通过回边到达的最小时间戳inttot;// 时间戳计数器intcnt;// 点双连通分量计数器stackintstk;// 栈存储当前正在处理的节点vectorintdcc[N];// 存储每个点双连通分量包含的节点// ---------- 割点相关 ----------intcut[N];// 标记节点是否为割点1表示是割点introot;// 当前 DFS 树的根节点intnum;// 方案数用于统计intid[N];// 未使用的数组保留原样// Tarjan 算法求点双连通分量 voidtarjan(intx){dfn[x]low[x]tot;// 初始化时间戳stk.push(x);// 当前节点入栈// 孤立点单独形成一个点双连通分量if(!e[x].size()){dcc[cnt].push_back(x);return;}intchild0;// 记录当前节点在 DFS 树中的子节点数// 遍历 x 的所有邻接点for(inty:e[x]){if(!dfn[y])// y 尚未访问{tarjan(y);// 递归访问 ylow[x]min(low[x],low[y]);// 用子树更新 low[x]// 判断 x 是否为割点if(low[y]dfn[x]){child;// 如果 x 不是根节点或者 x 是根节点且有多个子节点if(x!root||child1)cut[x]true;// 找到一个点双连通分量cnt;while(1){intzstk.top();// 取出栈顶stk.pop();// 弹出栈顶dcc[cnt].push_back(z);// 将节点加入当前分量if(zy)// 直到弹出 y 为止break;}dcc[cnt].push_back(x);// 将 x 也加入当前分量}}else// 发现回边{low[x]min(low[x],dfn[y]);// 用回边更新 low[x]}}}// 主函数 intmain(){intT1;// 测试用例编号// 多组测试数据直到 m 0 结束while(cinm,m){// 清空上一组数据for(inti1;icnt;i)dcc[i].clear();for(inti1;in;i)e[i].clear();while(!stk.empty())stk.pop();// 重置计数器totcntn0;memset(cut,0,sizeof(cut));memset(dfn,0,sizeof(dfn));// 读入 m 条边while(m--){inta,b;cinab;nmax(n,a);// 更新最大节点编号nmax(n,b);e[a].push_back(b);// 添加无向边e[b].push_back(a);}// 对每个未访问的节点执行 Tarjan 算法for(root1;rootn;root)if(!dfn[root])tarjan(root);// 统计答案 intres0;// 最少需要放置的消防站数量ULL num1;// 方案数// 遍历每个点双连通分量for(inti1;icnt;i){inttmp0;// 当前分量中割点的数量// 统计当前分量中割点的个数for(intj0;jdcc[i].size();j)if(cut[dcc[i][j]])tmp;// 情况1分量中没有割点if(tmp0){// 孤立点需要放 1 个消防站if(dcc[i].size()1)res1;// 非孤立点需要放 2 个消防站方案数为 C(size, 2)else{res2;num*(ULL)dcc[i].size()*(dcc[i].size()-1)/2;}}// 情况2分量中有 1 个割点elseif(tmp1){res;// 需要在非割点中放 1 个消防站num*dcc[i].size()-1;// 方案数为非割点个数}// 情况3分量中有 2 个及以上割点无需放置消防站}// 输出结果printf(Case %d: %d %llu\n,T,res,num);}return0;}【运行结果】9 1 3 4 1 3 5 1 2 2 6 1 5 6 3 1 6 3 2 Case 1: 2 4 6 1 2 1 3 2 4 2 5 3 6 3 7 Case 2: 4 1 0
题解：AcWing 396 矿场搭建
发布时间：2026/6/22 10:03:24
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing396. 矿场搭建 - AcWing题库【题目描述】煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口使得无论哪一个挖煤点坍塌之后其他挖煤点的工人都有一条道路通向救援出口。请写一个程序用来计算至少需要设置几个救援出口以及不同最少救援出口的设置方案总数。【输入】输入文件有若干组数据每组数据的第一行是一个正整数N NN表示工地的隧道数。接下来的N NN行每行是用空格隔开的两个整数S SS和T TTS ≠ T S≠TST表示挖煤点S SS与挖煤点T TT由隧道直接连接。注意每组数据的挖煤点的编号为1 ∼ M a x 1∼Max1∼Max其中M a x MaxMax表示由隧道连接的挖煤点中编号最大的挖煤点的编号可能存在没有被隧道连接的挖煤点。输入数据以0 00结尾。【输出】每组数据输出结果占一行。其中第i ii行以Case i:开始注意大小写Case与i之间有空格i与:之间无空格:之后有空格。其后是用空格隔开的两个正整数第一个正整数表示对于第i ii组输入数据至少需要设置几个救援出口第二个正整数表示对于第i ii组输入数据不同最少救援出口的设置方案总数。输入数据保证答案小于2 64 2^{64}264输出格式参照以下输入输出样例。【输入样例】9 1 3 4 1 3 5 1 2 2 6 1 5 6 3 1 6 3 2 6 1 2 1 3 2 4 2 5 3 6 3 7 0【输出样例】Case 1: 2 4 Case 2: 4 1【核心思想】问题分析给定一个无向图需要在某些节点设置救援出口使得删除任意一个节点挖煤点坍塌后剩余节点都能到达某个救援出口。这等价于求点双连通分量中的割点分布并在每个点双连通分量中合理设置出口。算法选择Tarjan 算法求点双连通分量通过d f n dfndfn和l o w lowlow数组找出图中的所有点双连通分量割点判定利用l o w [ y ] ≥ d f n [ x ] low[y] \geq dfn[x]low[y]≥dfn[x]判断节点x xx是否为割点分类讨论根据每个点双连通分量中割点的数量决定需要设置的出口数量和方案数关键步骤建图读入m mm条边构建无向图邻接表确定最大节点编号n nnTarjan 求点双连通分量对每个未访问的节点作为根节点执行t a r j a n ( r o o t ) tarjan(root)tarjan(root)使用栈维护当前 DFS 路径上的节点当发现l o w [ y ] ≥ d f n [ x ] low[y] \geq dfn[x]low[y]≥dfn[x]时找到一个点双连通分量将栈中节点弹出直到y yy统计每个分量中的割点数量t m p tmptmp情况1t m p 0 tmp 0tmp0无割点若分量大小为1 11孤立点需要设置1 11个出口方案数× 1 \times 1×1若分量大小≥ 2 \geq 2≥2需要设置2 22个出口方案数× C ( s i z e , 2 ) s i z e × ( s i z e − 1 ) 2 \times C(size, 2) \frac{size \times (size-1)}{2}×C(size,2)2size×(size−1)情况2t m p 1 tmp 1tmp1一个割点需要设置1 11个出口在非割点位置方案数× ( s i z e − 1 ) \times (size - 1)×(size−1)情况3t m p ≥ 2 tmp \geq 2tmp≥2多个割点该分量被多个割点保护无需设置出口输出答案最少出口数r e s resres和总方案数n u m numnum时间/空间复杂度时间复杂度O ( n m ) O(n m)O(nm)Tarjan 算法线性遍历所有节点和边空间复杂度O ( n m ) O(n m)O(nm)存储图结构和辅助数组点双连通分量与割点的核心思想点双连通分量图中删除任意一个节点后仍然连通的极大子图割点作用割点是连接不同点双连通分量的桥梁删除割点会将图分割成多个连通块出口设置策略无割点的分量必须内部设置出口且至少2 22个防止出口所在点坍塌有一个割点的分量割点坍塌时分量孤立需在非割点设1 11个出口有多个割点的分量任意点坍塌都能通过其他割点逃出无需设出口孤立点特判单个孤立点只需设置1 11个出口自己就是出口适用于网络可靠性、关键节点识别、冗余设计类问题【算法标签】#双连通分量【代码详解】#includebits/stdc.husingnamespacestd;// 定义无符号长整型别名用于存储方案数typedefunsignedlonglongULL;// 常量与全局变量 constintN1005;// 最大节点数intn;// 当前测试用例的节点数intm;// 当前测试用例的边数vectorinte[N];// 原图邻接表vectorintne[N];// 未使用的邻接表保留原样// ---------- Tarjan 相关 ----------intdfn[N];// 时间戳节点首次被访问的顺序intlow[N];// 能通过回边到达的最小时间戳inttot;// 时间戳计数器intcnt;// 点双连通分量计数器stackintstk;// 栈存储当前正在处理的节点vectorintdcc[N];// 存储每个点双连通分量包含的节点// ---------- 割点相关 ----------intcut[N];// 标记节点是否为割点1表示是割点introot;// 当前 DFS 树的根节点intnum;// 方案数用于统计intid[N];// 未使用的数组保留原样// Tarjan 算法求点双连通分量 voidtarjan(intx){dfn[x]low[x]tot;// 初始化时间戳stk.push(x);// 当前节点入栈// 孤立点单独形成一个点双连通分量if(!e[x].size()){dcc[cnt].push_back(x);return;}intchild0;// 记录当前节点在 DFS 树中的子节点数// 遍历 x 的所有邻接点for(inty:e[x]){if(!dfn[y])// y 尚未访问{tarjan(y);// 递归访问 ylow[x]min(low[x],low[y]);// 用子树更新 low[x]// 判断 x 是否为割点if(low[y]dfn[x]){child;// 如果 x 不是根节点或者 x 是根节点且有多个子节点if(x!root||child1)cut[x]true;// 找到一个点双连通分量cnt;while(1){intzstk.top();// 取出栈顶stk.pop();// 弹出栈顶dcc[cnt].push_back(z);// 将节点加入当前分量if(zy)// 直到弹出 y 为止break;}dcc[cnt].push_back(x);// 将 x 也加入当前分量}}else// 发现回边{low[x]min(low[x],dfn[y]);// 用回边更新 low[x]}}}// 主函数 intmain(){intT1;// 测试用例编号// 多组测试数据直到 m 0 结束while(cinm,m){// 清空上一组数据for(inti1;icnt;i)dcc[i].clear();for(inti1;in;i)e[i].clear();while(!stk.empty())stk.pop();// 重置计数器totcntn0;memset(cut,0,sizeof(cut));memset(dfn,0,sizeof(dfn));// 读入 m 条边while(m--){inta,b;cinab;nmax(n,a);// 更新最大节点编号nmax(n,b);e[a].push_back(b);// 添加无向边e[b].push_back(a);}// 对每个未访问的节点执行 Tarjan 算法for(root1;rootn;root)if(!dfn[root])tarjan(root);// 统计答案 intres0;// 最少需要放置的消防站数量ULL num1;// 方案数// 遍历每个点双连通分量for(inti1;icnt;i){inttmp0;// 当前分量中割点的数量// 统计当前分量中割点的个数for(intj0;jdcc[i].size();j)if(cut[dcc[i][j]])tmp;// 情况1分量中没有割点if(tmp0){// 孤立点需要放 1 个消防站if(dcc[i].size()1)res1;// 非孤立点需要放 2 个消防站方案数为 C(size, 2)else{res2;num*(ULL)dcc[i].size()*(dcc[i].size()-1)/2;}}// 情况2分量中有 1 个割点elseif(tmp1){res;// 需要在非割点中放 1 个消防站num*dcc[i].size()-1;// 方案数为非割点个数}// 情况3分量中有 2 个及以上割点无需放置消防站}// 输出结果printf(Case %d: %d %llu\n,T,res,num);}return0;}【运行结果】9 1 3 4 1 3 5 1 2 2 6 1 5 6 3 1 6 3 2 Case 1: 2 4 6 1 2 1 3 2 4 2 5 3 6 3 7 Case 2: 4 1 0
