题目大意：有n条隧道和一些连接点，要在一些连接点修建逃生装置，使得不管哪个点发生坍塌，其他点的人都可以从逃生。让你求出应该安装的最少逃生装置的数量和方案数。
解题思路：经过了上一题，这一题其实还比较好想。一张图，点会坍塌，然后逃生，很容易想到割顶。然后发现用割顶装逃生装置是不合算的，不是割顶的才好。对于一个双连通分量，只有一个割顶的需要在任何一个非割顶的点装就行了。割顶数>=2个的，不需要装，反正有路能跑到其他地方去。然后还有一点容易忽略，我也开始没想到：如果整张图没有割顶，那么就是任选两个点装逃生装置，方案数是 V*(V-1)/2，V 为 点数。
一开始交错题号了，一直WA，还检查了老半天。。 = =
代码如下：
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long lld;
const int MAXN = 50005<<1;
struct Edge
{
int u,v;
};
vector <int> G[MAXN],bcc[MAXN];
stack <Edge> S;
int pre[MAXN],is_cut[MAXN],bccno[MAXN];
int bcc_cnt,dfs_clock;
int dfs(int u,int fa)
{
int low_u = pre[u] = ++dfs_clock;
int child = 0;
for(int i = 0;i < G[u].size();i++)
{
int v = G[u][i];
Edge e = (Edge){u,v};
if(!pre[v])
{
child++;
S.push(e);
int low_v = dfs(v,u);
low_u = min(low_u,low_v);
if(low_v >= pre[u])
{
is_cut[u] = 1;
bcc_cnt++;
bcc[bcc_cnt].clear();
for(;;)
{
Edge x = S.top();
S.pop();
if(bccno[x.u] != bcc_cnt)
{
bcc[bcc_cnt].push_back(x.u);
bccno[x.u] = bcc_cnt;
}
if(bccno[x.v] != bcc_cnt)
{
bcc[bcc_cnt].push_back(x.v);
bccno[x.v] = bcc_cnt;
}
if(x.u == u && x.v == v)
break;
}
}
}
else if(pre[v] < pre[u] && v != fa)
{
S.push(e);
low_u = min(low_u,pre[v]);
}
}
if(child == 1 && fa == -1) is_cut[u] = 0;
return low_u;
}
void find_bcc(int n)
{
memset(pre,0,sizeof(pre));
memset(is_cut,0,sizeof(is_cut));
memset(bccno,0,sizeof(bccno));
dfs_clock = bcc_cnt = 0;
for(int i = 0;i < n;i++)
if(!pre[i]) dfs(i,-1);
}
int main()
{
int cas = 0;
int n;
while(~scanf("%d",&n) && n)
{
for(int i = 0;i < 2*n;i++)
G[i].clear();
int max_id = 0;
for(int i = 0;i < n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
max_id = max(max_id,a);
max_id = max(max_id,b);
a--;b--;
G[a].push_back(b);
G[b].push_back(a);
}
find_bcc(max_id);
//printf("bcc_cnt = %d\n",bcc_cnt);
int ans_num = 0;
lld ans_count = 1;
if(bcc_cnt == 1)
{
ans_num = 2;
ans_count = (lld)bcc[1].size()*(bcc[1].size()-1)/2;
}
else
{
for(int i = 1;i <= bcc_cnt;i++)
{
int cc = 0;
for(int j = 0;j < bcc[i].size();j++)
if(is_cut[bcc[i][j]] == 1)
cc++;
if(cc == 1)
{
ans_num++;
ans_count *= bcc[i].size()-1;
}
}
}
printf("Case %d: %d %lld\n",++cas,ans_num,ans_count);
}
return 0;
}
另外一种，也就是只做找割顶，不做BCC，其实差不多，基本思路一样。就是先找出所有割顶，然后对对不是割顶的点进行dfs，找遍这个连通分量的所有点，过程中不经过割顶，但记录个数，如果数目是1，就更新答案（更新方法和上面一样）。同样，也要特判割顶为0的情况。
代码如下：
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long lld;
const int MAXN = 50005<<1;
vector <int> G[MAXN];
int pre[MAXN],is_cut[MAXN];
int dfs_clock;
int dfs(int u,int fa)
{
int low_u = pre[u] = ++dfs_clock;
int child = 0;
for(int i = 0;i < G[u].size();i++)
{
int v = G[u][i];
if(!pre[v])
{
child++;
int low_v = dfs(v,u);
low_u = min(low_u,low_v);
if(low_v >= pre[u])
{
is_cut[u] = 1;
}
}
else if(pre[v] < pre[u] && v != fa)
{
low_u = min(low_u,pre[v]);
}
}
if(child == 1 && fa == -1) is_cut[u] = 0;
return low_u;
}
void find_bcc(int n)
{
memset(pre,0,sizeof(pre));
memset(is_cut,0,sizeof(is_cut));
dfs_clock = 0;
for(int i = 0;i < n;i++)
if(!pre[i]) dfs(i,-1);
}
int vis[MAXN];
vector <int> cut;
void dfs1(int u,int& cc,int& tot)
{
vis[u] = 1;
tot++;
for(int i = 0;i < G[u].size();i++)
{
int v = G[u][i];
if(!vis[v])
{
if(is_cut[v])
{
vis[v] = 1;
cc++;
cut.push_back(v);
continue;
}
dfs1(v,cc,tot);
}
}
}
int main()
{
int cas = 0;
int n;
while(~scanf("%d",&n) && n)
{
for(int i = 0;i < 2*n;i++)
G[i].clear();
int max_id = 0;
for(int i = 0;i < n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
max_id = max(max_id,a);
max_id = max(max_id,b);
a--;b--;
G[a].push_back(b);
G[b].push_back(a);
}
find_bcc(max_id);
int ans_num = 0;
lld ans_count = 1;
int cc = 0;
for(int i = 0;i < max_id;i++)
if(is_cut[i])
cc++;
if(cc == 0)
{
ans_num = 2;
ans_count = (lld)max_id*(max_id-1)/2;
}
else
{
memset(vis,0,sizeof(vis));
for(int i = 0;i < max_id;i++)
if(!vis[i] && !is_cut[i])
{
int cc = 0;
int tot = 0;
cut.clear();
dfs1(i,cc,tot);
if(cc == 1)
{
ans_num++;
ans_count *= tot;
}
for(int j = 0;j < cut.size();j++)
vis[cut[j]] = 0;
}
}
printf("Case %d: %d %lld\n",++cas,ans_num,ans_count);
}
return 0;
}
/*
6
1 2
1 3
2 3
3 4
3 5
4 5
*/