题目概述

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。

解题报告

万年神坑点双连通分量，先求出所有的割点($low[son]\ge dfn[x]$)，然后分类讨论：

1. 没有割点，为了避免一个塌了所以需要两个，那么答案就是 $2$ ，方案 $n\choose2$ 。
2. 一个点双中有一个割点，点双内需要建一个防止割点塌了，那么答案加上 $1$ ，方案乘上 $size$ 。

示例程序

SB题毁我青春，点数据范围没给，也没说有没有自环之类的，反正改了挺久。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxm=500,maxn=10000;

int n,S,T,ti,dfn[maxn+5],low[maxn+5],top,stk[maxn+5],A;LL B;
int E,lnk[maxn+5],son[(maxm<<1)+5],nxt[(maxm<<1)+5];
bool PBC[maxn+5],vis[maxn+5];int tot,now[maxn+5],si[maxn+5],sum[maxn+5];

#define Add(x,y) (son[E]=(y),nxt[E]=lnk[x],lnk[x]=E++)
void Tarjan(int x,int pre=-1){
    dfn[x]=low[x]=++ti;stk[++top]=x;int tot=0;
    for (int j=lnk[x],u;~j;j=nxt[j])
        if ((j^1)!=pre) if (!dfn[u=son[j]]){
                Tarjan(u,j);low[x]=min(low[x],low[u]);tot++;
                if (low[u]>=dfn[x]) PBC[x]=true;
            } else low[x]=min(low[x],dfn[u]);
    if (pre<0&&tot==1) PBC[x]=false;
}
void Dfs(int x,int pre=-1){
    if (vis[x]) return;vis[x]=true;si[tot]++;
    for (int j=lnk[x];~j;vis[son[j]]=true,j=nxt[j])
        if ((j^1)!=pre) if (PBC[son[j]]) {sum[tot]+=now[son[j]]<tot;now[son[j]]=tot;continue;} else Dfs(son[j],j);
}
#define C2(x) ((LL)(x)*((x)-1)>>1)
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (int t=(scanf("%d",&n),1);n;scanf("%d",&n),t++){
        memset(lnk,255,sizeof(lnk));ti=0;memset(dfn,0,sizeof(dfn));A=0;B=1;
        for (int i=1,x,y;i<=n;i++) scanf("%d%d",&x,&y),Add(x,y),Add(y,x);
        memset(PBC,0,sizeof(PBC));memset(vis,0,sizeof(vis));tot=0;
        for (int i=1;i<=maxn;i++) if (!dfn[i]&&~lnk[i]) Tarjan(i);memset(now,0,sizeof(now));
        for (int i=1;i<=maxn;i++) if (!vis[i]&&!PBC[i]&&~lnk[i]) tot++,si[tot]=sum[tot]=0,Dfs(i);
        for (int i=1;i<=tot;i++)
            if (sum[i]==0) A+=2,B*=C2(si[i]);
            else if (sum[i]==1) A+=1,B*=si[i];
        printf("Case %d: %d %lld\n",t,A,B);
    }
    return 0;
}