P3225 [HNOI2012]矿场搭建

传送门

对于一个点双联通分量，如果它连接了两个或更多割点

那么不论哪个点GG都有至少一条路通到其他的点双联通分量，所以我们不用考虑

如果它只连接一个割点，如果这个割点GG，那整个块也一起GG，所以要再这个块里建一个出口

如果它没有连接割点，只建一个出口还不够，可能这个出口所在的点GG，所以要两个出口

那么三种情况的各自的方案数分别为

1 (啥都不干)

块内点的大小 (块内的每个点都可以建出口)

$C_{块内点的大小}^2$ (块内顺便选两个点建出口)

根据乘法原理把每个块的方案数乘起来就是总方案数了

然后Tarjan求出所有割点和点双联通分量就好了

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<vector>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=1e4+;

int fir[N],from[N<<],to[N<<],cntt;

inline void add(int &a,int &b)

{

    from[++cntt]=fir[a];

    fir[a]=cntt; to[cntt]=b;

}

int dfs_clock,dfn[N],low[N],st[N],Top,cut[N],rt,tot;

vector <int> be[N];//be[i][j]存属于第i个块的第j个点

void Tarjan(int x)//Tarjan模板求割点

{

    dfn[x]=low[x]=++dfs_clock; st[++Top]=x;

    int ch=;

    for(int i=fir[x];i;i=from[i])

    {

        int &v=to[i];

        if(!dfn[v])

        {

            Tarjan(v); ch++;

            low[x]=min(low[x],low[v]);

            if((x==rt&&ch>)||(x!=rt&&dfn[x]<=low[v])) cut[x]=;//注意节点为根时要特判

            if(dfn[x]<=low[v])

            {

                be[++tot].clear();//注意多组数据

                while(st[Top]!=v)

                    be[tot].push_back(st[Top--]);

                be[tot].push_back(st[Top--]);

                be[tot].push_back(x);//把割点也算进相邻的点双，方便统计

            }

        }

        else low[x]=min(low[x],dfn[v]);

    }

}

int n,m;

ll ans1,ans2;

int main()

{

    int a,b,num=;

    while(scanf("%d",&m)&&m)

    {

        memset(cut,,sizeof(cut));

        memset(dfn,,sizeof(dfn));

        memset(low,,sizeof(low));

        memset(fir,,sizeof(fir));

        n=tot=dfs_clock=Top=cntt=ans1=; ans2=;//初始化

        for(int i=;i<=m;i++)

        {

            a=read(); b=read();

            add(a,b); add(b,a);

            n=max(n,max(a,b));//节点数还要自己求

        }

        for(int i=;i<=n;i++) if(!dfn[i]) rt=i,Tarjan(i);

        for(int i=;i<=tot;i++)

        {

            int len=be[i].size(),cnt=;

            for(int j=;j<len;j++) cnt+=cut[be[i][j]];//记录割点个数

            if(!cnt)//如果没割点

                ans1+=2,ans2*=((1ll*len*(len-))>>);

            else if(cnt==) ans1++,ans2*=(len-);//注意len-1,因为len包括一个割点

        }

        printf("Case %d: %lld %lld\n",++num,ans1,ans2);

    }

    return ;

}