洛谷3225 [HNOI2012]矿场搭建

题意

给出一个无向图，要求在一些节点设置出口，要求任意一个节点爆了以后所有节点都能到达出口。

其中边数 $M\le 500$ ，点数要自己推。

题解

先求出割点，然后对每个双连通分量求出节点个数 $siz$ 和割点个数 $cut$ ，分类讨论：

1. 双连通分量里没有割点，那么它无法与外界连通，只能自己内部修 $2$ 个出口，方案数为 $\dfrac {siz\times \left( siz-1\right) }{2}$ 。
2. 有 $1$ 个割点，如果是割点炸了，需要自己修一个；如果是非割点炸了，那么可以通过割点到达其它双连通分量。所以修 $1$ 个即可，方案数为 $siz$
3. 有 $2$ 个割点，那无论什么点炸了都可以跑到其它双连通分量，不用修。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    ll next,to;
} edge[505];
bool is_cut[1005];
ll cnt,head[1005],n,m,a,b,kase,vis[1005];
ll id[1005],low[1005],scc[1005],dfsord,scnt,siz,cut;

inline void add(ll u,ll v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(ll x,ll f)
{
    id[x]=low[x]=++dfsord;
    ll ch=0;
    for (ll i=head[x];i;i=edge[i].next)
    {
        ll y=edge[i].to;
        if (!id[y])
        {
            dfs(y,x);
            ch++;
            low[x]=min(low[x],low[y]);
            if ((!f && ch>1) || (f && id[x]==low[y])) is_cut[x]=1;
        }
        else if (!scc[y]) low[x]=min(low[x],id[y]);
    }
}

void dfs2(ll x,ll gcnt)
{
    vis[x]=gcnt;
    siz++;
    for (ll i=head[x];i;i=edge[i].next)
    {
        ll y=edge[i].to;
        if (is_cut[y] && vis[y]!=gcnt)
        {
            cut++;
            vis[y]=gcnt;
        }
        if (!vis[y]) dfs2(y,gcnt);
    }
}

inline void init()
{
    n=cnt=scnt=dfsord=0;
    memset(id,0,sizeof(id));
    memset(low,0,sizeof(low));
    memset(scc,0,sizeof(scc));
    memset(vis,0,sizeof(vis));
    memset(head,0,sizeof(head));
    memset(is_cut,0,sizeof(is_cut));
}

int main()
{
    while (~scanf("%lld",&m) && m)
    {
        init();
        for (ll i=1;i<=m;i++)
        {
            a=read(); b=read();
            add(a,b);
            add(b,a);
            n=max(n,max(a,b));
        }
        for (ll i=1;i<=n;i++)
        {
            if (id[i]) continue;
            dfs(i,0);
        }
        ll gcnt=0,ans1=0,ans2=1;
        for (ll i=1;i<=n;i++)
        {
            if (vis[i] || is_cut[i]) continue;
            siz=cut=0;
            dfs2(i,++gcnt);
            if (cut>1) continue;
            if (cut) ans1++,ans2*=siz;
            else ans1+=2,ans2*=(siz*(siz-1))>>1;
        }
        printf("Case %lld: %lld %lld\n",++kase,ans1,ans2);
    }
    return 0;
}