题面
题面提取
给定一个无向图（可能不连通），需要在某些节点设置出口，使得无论图中哪个节点坍塌（被删除），其他所有节点都能到达至少一个出口。要求求出最少需要设置多少个出口，以及在最少出口情况下的方案数。
解题思路
这是一道典型的图论问题，需要用到割点和点双连通分量的概念。
- 割点：如果一个节点被删除后，图的连通分量数量增加，那么这个节点就是割点。
- 点双连通分量：不包含割点的极大连通子图。
解题步骤：
- 使用 Tarjan 算法找出所有割点。
- 求出所有的点双连通分量。
- 对于每个点双连通分量：
- 如果没有割点，需要设置2个出口（防止其中一个出口坍塌），方案数为 C(size,2)。
- 如果有 1 个割点，需要设置 1 个出口（如果割点坍塌，可以通过这个出口逃生），方案数为 size-1。
- 如果有 2 个及以上割点，不需要设置出口（可以通过其他分量的出口逃生）。
- 将所有分量的结果相乘得到总方案数。
代码实现（含注释）：
/*信友队保佑AC！！*/
#include <bits/stdc++.h>
using namespace std;
const int N = 505; // 最大节点数
vector<int> G[N]; // 图的邻接表表示
int dfn[N]; // DFS访问顺序编号
int low[N]; // 通过回边能到达的最小编号
int cut[N]; // 标记节点是否为割点
int n, m; // n:实际节点数，m:边数
int idx; // DFS时间戳
int cnt; // 点双连通分量计数器
stack<int> st; // 用于Tarjan算法的栈
vector<int> dcc[N];// 存储每个点双连通分量中的节点
/* Tarjan算法求割点和点双连通分量
u:当前节点, root:DFS树的根节点 */
void tarjan(int u, int root)
{
dfn[u] = low[u] = ++idx; // 初始化dfn和low
st.push(u); // 节点入栈
int child = 0; // 记录DFS树中子节点数量
for (int v : G[u]) // 遍历所有邻接节点
{
if (!dfn[v]) // 如果v未被访问过
{
tarjan(v, root); // 递归访问v
low[u] = min(low[u], low[v]); // 更新low值
// 判断是否为割点
if (low[v] >= dfn[u])
{
child++;
// 如果不是根节点或者是根节点但有多个子树
if (u != root || child > 1)
{
cut[u] = 1; // 标记为割点
}
// 找到一个点双连通分量
cnt++;
dcc[cnt].clear(); // 清空当前分量
// 弹出栈中节点直到v，这些节点构成一个点双连通分量
while (true)
{
int x = st.top();
st.pop();
dcc[cnt].push_back(x);
if (x == v)
{
break;
}
}
dcc[cnt].push_back(u); // 把u也加入分量
}
}
else // 如果v已被访问过，是回边
{
low[u] = min(low[u], dfn[v]); // 更新low值
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 0; // 测试用例编号
while (cin >> m, m) // 循环处理每个测试用例
{
// 初始化
for (int i = 0; i < N; i++)
{
G[i].clear();
}
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(cut, 0, sizeof(cut));
n = idx = cnt = 0;
// 读入图
for (int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
n = max(n, max(u, v)); // 更新实际节点数
}
// 寻找所有点双连通分量
for (int i = 1; i <= n; i++)
{
if (!dfn[i]) // 如果未访问过
{
tarjan(i, i); // 以i为根进行Tarjan算法
}
}
// 计算结果
unsigned long long ans1 = 0, ans2 = 1; // ans1:最少出口数，ans2:方案数
for (int i = 1; i <= cnt; i++) // 遍历每个点双连通分量
{
int num = 0; // 该分量中割点数量
int sz = dcc[i].size(); // 该分量中节点数
// 统计该分量中的割点数量
for (int u : dcc[i])
{
if (cut[u])
{
num++;
}
}
// 根据割点数量决定出口设置方案
if (num == 0) // 无割点，需要设置2个出口
{
ans1 += 2;
ans2 *= sz * (sz - 1) / 2; // C(sz,2)种选择
}
else if (num == 1) // 1个割点，需要设置1个出口
{
ans1 += 1;
ans2 *= sz - 1; // 不能选割点，所以有(sz-1)种选择
}
// 有2个及以上割点不需要设置出口
}
// 输出结果
cout << "Case " << ++T << ": " << ans1 << " " << ans2 << endl;
}
return 0;
}
// 完结，散花 ^_^ ^_^
代码实现（无注释）：
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
vector<int> G[N];
int dfn[N], low[N], cut[N];
int n, m, idx, cnt;
stack<int> st;
vector<int> dcc[N];
void tarjan(int u, int root)
{
dfn[u] = low[u] = ++idx;
st.push(u);
int child = 0;
for (int v : G[u])
{
if (!dfn[v])
{
tarjan(v, root);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u])
{
child++;
if (u != root || child > 1)
{
cut[u] = 1;
}
cnt++;
dcc[cnt].clear();
while (true)
{
int x = st.top();
st.pop();
dcc[cnt].push_back(x);
if (x == v)
{
break;
}
}
dcc[cnt].push_back(u);
}
}
else
{
low[u] = min(low[u], dfn[v]);
}
}
}
int main()
{
// freopen ( ".in", "r", stdin );
// freopen ( ".out", "w", stdout );
ios::sync_with_stdio ( false );
cin.tie ( 0 );
cout.tie ( 0 );
int T = 0;
while (cin >> m, m)
{
for (int i = 0; i < N; i++)
{
G[i].clear();
}
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(cut, 0, sizeof(cut));
n = idx = cnt = 0;
for (int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
n = max(n, max(u, v));
}
for (int i = 1; i <= n; i++)
{
if (!dfn[i])
{
tarjan(i, i);
}
}
unsigned long long ans1 = 0, ans2 = 1;
for (int i = 1; i <= cnt; i++)
{
int num = 0;
int sz = dcc[i].size();
for (int u : dcc[i])
{
if (cut[u])
{
num++;
}
}
if (num == 0)
{
ans1 += 2;
ans2 *= sz * (sz - 1) / 2;
}
else if (num == 1)
{
ans1 += 1;
ans2 *= sz - 1;
}
}
cout << "Case " << ++T << ": " << ans1 << " " << ans2 << endl;
}
return 0;
}
样例测试：
AC记录：
感受：
这道题目综合考察了图论中的割点和双连通分量知识，难度适中但需要细心。
