题解：AcWing 396 矿场搭建

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

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

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

【题目来源】

AcWing：396. 矿场搭建 - AcWing题库

【题目描述】

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。

为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。

于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。

请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。

【输入】

输入文件有若干组数据，每组数据的第一行是一个正整数N NN，表示工地的隧道数。

接下来的N NN行每行是用空格隔开的两个整数S SS和T TT（S ≠ T S≠TS=T），表示挖煤点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

【核心思想】

1. 问题分析：给定一个无向图，需要在某些节点设置救援出口，使得删除任意一个节点（挖煤点坍塌）后，剩余节点都能到达某个救援出口。这等价于求点双连通分量中的割点分布，并在每个点双连通分量中合理设置出口。

2. 算法选择：

   • 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是否为割点
   • 分类讨论：根据每个点双连通分量中割点的数量，决定需要设置的出口数量和方案数

3. 关键步骤：

   • 建图：读入m mm条边，构建无向图邻接表，确定最大节点编号n nn
   • Tarjan 求点双连通分量：
     • 对每个未访问的节点作为根节点执行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：
     • 情况1（t m p = 0 tmp = 0tmp=0，无割点）：
       • 若分量大小为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)​
     • 情况2（t m p = 1 tmp = 1tmp=1，一个割点）：需要设置1 11个出口在非割点位置，方案数× ( s i z e − 1 ) \times (size - 1)×(size−1)
     • 情况3（t m p ≥ 2 tmp \geq 2tmp≥2，多个割点）：该分量被多个割点保护，无需设置出口
   • 输出答案：最少出口数r e s resres和总方案数n u m numnum

4. 时间/空间复杂度：

   • 时间复杂度：O ( n + m ) O(n + m)O(n+m)，Tarjan 算法线性遍历所有节点和边
   • 空间复杂度：O ( n + m ) O(n + m)O(n+m)，存储图结构和辅助数组

5. 点双连通分量与割点的核心思想：

   • 点双连通分量：图中删除任意一个节点后仍然连通的极大子图
   • 割点作用：割点是连接不同点双连通分量的"桥梁"，删除割点会将图分割成多个连通块
   • 出口设置策略：
     • 无割点的分量：必须内部设置出口，且至少2 22个（防止出口所在点坍塌）
     • 有一个割点的分量：割点坍塌时分量孤立，需在非割点设1 11个出口
     • 有多个割点的分量：任意点坍塌都能通过其他割点逃出，无需设出口
   • 孤立点特判：单个孤立点只需设置1 11个出口（自己就是出口）
   • 适用于网络可靠性、关键节点识别、冗余设计类问题

【算法标签】

#双连通分量

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;// 定义无符号长整型别名，用于存储方案数typedefunsignedlonglongULL;// ================= 常量与全局变量 =================constintN=1005;// 最大节点数intn;// 当前测试用例的节点数intm;// 当前测试用例的边数vector<int>e[N];// 原图邻接表vector<int>ne[N];// 未使用的邻接表（保留原样）// ---------- Tarjan 相关 ----------intdfn[N];// 时间戳：节点首次被访问的顺序intlow[N];// 能通过回边到达的最小时间戳inttot;// 时间戳计数器intcnt;// 点双连通分量计数器stack<int>stk;// 栈，存储当前正在处理的节点vector<int>dcc[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;}intchild=0;// 记录当前节点在 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||child>1)cut[x]=true;// 找到一个点双连通分量cnt++;while(1){intz=stk.top();// 取出栈顶stk.pop();// 弹出栈顶dcc[cnt].push_back(z);// 将节点加入当前分量if(z==y)// 直到弹出 y 为止break;}dcc[cnt].push_back(x);// 将 x 也加入当前分量}}else// 发现回边{low[x]=min(low[x],dfn[y]);// 用回边更新 low[x]}}}// ================= 主函数 =================intmain(){intT=1;// 测试用例编号// 多组测试数据，直到 m = 0 结束while(cin>>m,m){// 清空上一组数据for(inti=1;i<=cnt;i++)dcc[i].clear();for(inti=1;i<=n;i++)e[i].clear();while(!stk.empty())stk.pop();// 重置计数器tot=cnt=n=0;memset(cut,0,sizeof(cut));memset(dfn,0,sizeof(dfn));// 读入 m 条边while(m--){inta,b;cin>>a>>b;n=max(n,a);// 更新最大节点编号n=max(n,b);e[a].push_back(b);// 添加无向边e[b].push_back(a);}// 对每个未访问的节点执行 Tarjan 算法for(root=1;root<=n;root++)if(!dfn[root])tarjan(root);// ========= 统计答案 =========intres=0;// 最少需要放置的消防站数量ULL num=1;// 方案数// 遍历每个点双连通分量for(inti=1;i<=cnt;i++){inttmp=0;// 当前分量中割点的数量// 统计当前分量中割点的个数for(intj=0;j<dcc[i].size();j++)if(cut[dcc[i][j]])tmp++;// 情况1：分量中没有割点if(tmp==0){// 孤立点：需要放 1 个消防站if(dcc[i].size()==1)res+=1;// 非孤立点：需要放 2 个消防站，方案数为 C(size, 2)else{res+=2;num*=(ULL)dcc[i].size()*(dcc[i].size()-1)/2;}}// 情况2：分量中有 1 个割点elseif(tmp==1){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