最近在学图论相关的内容，阅读这篇博客的前提是你已经基本了解了Tarjan求点双。

由割点的定义（删去这个点就可使这个图不连通）我们可以知道，坍塌的挖煤点只有在割点上才会使这个图不连通，而除了割点的其他点上则无可厚非，所以我们只需要考虑这个图的割点的情况。

那么我们就可以求出所有的点双连通分量， 如果这个点双仅有一个割点，那么这个割点坍塌后这个点双就被“孤立”了，所以需要在这个点双里设置一个救援出口。

那么这个点双如果包含多个割点呢？假设它的其中一个割点坍塌了，它还可以从另外几个割点出去。

所以我们只需要判断有几个点双只有一个割点，便是我们要设置的救援出口的数量。

有的同学可能要问了，如果所有点双都有多个割点呢?这种情况是不存在的，因为如果这样所有点双都变得联通了，也就不存在点双了。

关于方案的总数，只需要运用乘法原理。需要注意的是如果整个图就是一个点双，那么救援出口应该是两个，方案数是节点数\(n\),\(n*(n-1)/2\)。

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define N 510#define LL long longLL vis[N],ans1,ans2=1,bcc[N],n,m,num,cntd,DFN[N],IsCut[N],low[N],belong[N];vector 
         
           G[N];vector 
          
            vecd[N];struct edge { int u,v; edge() {}; edge(int U,int V) {u=U;v=V;}};stack 
           
             st;LL read() { LL f=1,s=0;char a=getchar(); while(!(a>='0'&&a<='9')) { if(a=='-') f=-1 ; a=getchar(); } while(a>='0'&&a<='9') { s=s*10+a-'0'; a=getchar();} return f*s;}void init() { memset(bcc,0,sizeof(bcc)); memset(DFN,0,sizeof(DFN)); memset(vis,0,sizeof(vis)); memset(IsCut,0,sizeof(IsCut)); memset(belong,0,sizeof(belong)); memset(low,0,sizeof(low)); for(int i=1;i<=N;i++) G[i].clear(),vecd[i].clear(); for(LL i=1,u,v;i<=m;i++) { u=read();v=read(); vis[u]=vis[v]=1; G[u].push_back(v); G[v].push_back(u); } ans1=cntd=0; ans2=1;}void Tarjan(LL u,LL fa) { LL child=0; DFN[u]=low[u]=++num; for(LL i=0;i
            
             =DFN[u]) { IsCut[u]=1; cntd++; for(;;) { edge x=st.top();st.pop(); if(belong[x.u] != cntd) {vecd[cntd].push_back(x.u); belong[x.u] = cntd;} if(belong[x.v] != cntd) {vecd[cntd].push_back(x.v); belong[x.v] = cntd;} if(x.u == u && x.v == v) break; } } low[u]=min(low[u],low[v]); } else if(DFN[u]>DFN[v] && v!=fa) low[u]=min(low[u],DFN[v]); } if(fa<0 && child==1) IsCut[u]=0;}int main() { int flag=0; while(cin>>m && m) { init(); flag++; for(int i=1;vis[i];i++) if(!DFN[i]) Tarjan(i,-1); for(LL i=1;i<=cntd;i++) { for(int j=0;j