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

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

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

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

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

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

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

代码

#include <iostream>

#include <vector>

#include <stack>

#include <cstring>

#include <cstdio>

using namespace std;

#define N 510

#define LL long long

LL vis[N],ans1,ans2=1,bcc[N],n,m,num,cntd,DFN[N],IsCut[N],low[N],belong[N];

vector <LL> G[N];

vector <LL> vecd[N];

struct edge {

    int u,v;

    edge() {};

    edge(int U,int V) {u=U;v=V;}

};

stack <edge> 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<G[u].size();i++) {

        LL v=G[u][i];

        if(!DFN[v]) {

            child++;

            st.push( edge(u,v) );

            Tarjan(v,u);

            if(low[v]>=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<vecd[i].size();j++)

                if(IsCut[vecd[i][j]]) bcc[i]++;//bcc统计第i个点双的割点数量

                if(bcc[i]==1){  //仅有一个割点，统计答案

                    ans1++;

                    ans2*=(vecd[i].size()-1);//乘法原理

                }

        }

        LL siz=vecd[1].size();

        if(!ans1) cout<<"Case "<<flag<<": "<<"2"<<' '<<siz*(siz-1)/2<<endl;//特判原图是不是点双

        else cout<<"Case "<<flag<<": "<<ans1<<' '<<ans2<<endl;

    }

}

巴特西

C++[Tarjan求点双连通分量，割点][HNOI2012]矿场搭建

代码

最新文章

热门文章