[BZOJ 2730]HNOI 2012鉱場構築|割点

まず最低数が明らかに1より大きい場合、1つの点を爆破することを考慮し、それが割点でなければ影響がなく、割点であれば爆破後の各連通ブロックに少なくとも1つの救援点を満たさなければならない.この図に割点がなければ2つの点を選んで置けばいいのですが、答えはC(n,2)です.そうでなければ、各割点を求め、この図を割点によっていくつかの連通ブロックに分割します.これらの連通ブロックを縮点するのは木の構造です.木の上のいずれかの辺が切れた後に分かれた2つのブロックに救援点があるようにするには、必ず各葉ブロックに救援点を置きます.すべての葉ブロックのsizeを乗せればいいです.

#include
#include
#include
#define N 1005
#define ll unsigned long long
#define clr(a) memset(a,0,sizeof(a))
#define t1 st[top]
using namespace std;
struct edge{
    int e,next;
}ed[N*2];
int n,m,i,j,ans1,ne,s,e,tim,ecc,cnt,a[N],dfn[N],low[N],size,cut[N];
ll ans2;
void add(int s,int e)
{
    ed[++ne].e=e;ed[ne].next=a[s];a[s]=ne;
}
void tarjan(int x,int fa)
{
    dfn[x]=low[x]=++tim;
    int cnt1=0;
    bool f=false;
    for (int j=a[x];j;j=ed[j].next)
        if (ed[j].e!=fa)
        {
            if (!dfn[ed[j].e]) tarjan(ed[j].e,x),cnt1++;
            low[x]=min(low[x],low[ed[j].e]);
            if (dfn[x]<=low[ed[j].e]) f=true;
        }
    if ((fa==-1&&cnt1>1)||(fa!=-1&&f)) cut[x]=1,cnt++;
}
void dfs(int x,int tim)
{
    dfn[x]=1;size++;
    for (int j=a[x];j;j=ed[j].next)
    {   
        if (cut[ed[j].e]&&dfn[ed[j].e]if (!dfn[ed[j].e]) dfs(ed[j].e,tim);
    }
}
int main()
{
    freopen("2730.in","r",stdin);
    freopen("2730.out","w",stdout);
    for (int t=1;;t++)
    {
        scanf("%d",&m);
        if (!m) return 0;
        n=ne=tim=ans1=cnt=0;
        clr(a);clr(dfn);clr(cut);
        for (i=1;i<=m;i++)
        {
            scanf("%d%d",&s,&e);
            add(s,e);add(e,s);
            n=max(n,max(s,e));
        }
        for (i=1;i<=n;i++) if (!dfn[i]) tarjan(i,-1);
        ans2=1ll;
        clr(dfn);
        if (cnt==0) ans1=2,ans2=(n*(n-1)/2);
        else 
            for (i=1;i<=n;i++)
            {
                cnt=0;
                if (!cut[i]&&!dfn[i]) size=0,dfs(i,i);
                if (cnt==1) ans2*=size,ans1++;
            }
        printf("Case %d: %d %llu
",t,ans1,ans2);
    }
}