1027 - Tarjan之点双连通分量 - 矿场搭建[HNOI2012]

传送门

Prereading

这是自从暑假学了Tarjan的无向图连通性后，第一次实干
感觉有点感觉

Analysis

如果一个联通块中不含割点，那么在这个联通块内就应该设置2个出口（万一有一个被炸了），方案数就是$C_{sze}^2$Csze2​
如果联通块中含有1个割点，那么在这个联通块内就应该设置1个出口（炸掉割点or炸掉块内出口，都可以走另一边），方案数就是$sze$sze的大小
如果含有多个割点，就不需要设置出口，因为任意一个被炸后，都可以另找出路

Code

#include<bits/stdc++.h>
#define in read()
#define ll long long
#define M 1009
using namespace std;
inline int read(){
    char ch;int f=1,res=0;
    while((ch=getchar())<'0'||ch>'9') if(ch=='-') f=-1;
    while(ch>='0'&&ch<='9'){
        res=(res<<3)+(res<<1)+ch-'0';
        ch=getchar();
    }
    return f==1?res:-res;
}
int n,m,key,sze,root,cnt,tot,num=0;
int to[M],nxt[M],head[M],ecnt=0;
int dfn[M],low[M],dfs=0,cut[M];
int vis[M];
ll ans1,ans2;
inline void add(int x,int y){
    nxt[++ecnt]=head[x];head[x]=ecnt;to[ecnt]=y;
}
inline void init(){
    ecnt=0;n=0;dfs=0;ans1=0;ans2=1;
    memset(vis,0,sizeof(vis));
    memset(head,0,sizeof(head));
    memset(cut,0,sizeof(cut));
    memset(dfn,0,sizeof(dfn));
}
inline void tarjan(int u){
    dfn[u]=low[u]=++dfs;
    int flag=0;
    for(int e=head[u];e;e=nxt[e]){
        int v=to[e];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[v],low[u]);
            if(low[v]>=dfn[u]){
                ++flag;
                if(flag>1||u!=root) cut[u]=1;
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}
void Dfs(int x){
    int i,j;
    vis[x]=num;
    if(cut[x])  return;
    tot++;
    for(i=head[x];i;i=nxt[i])
    {
        j=to[i];
        if(cut[j]&&vis[j]!=num)  cnt++,vis[j]=num;
        if(!vis[j])  Dfs(j);
    }
}
int main(){
    int cse=0;
    while(1){
        m=in;
        if(!m) break;
        init();
        int i,j,k,u,v;
        for(i=1;i<=m;++i){
            u=in;v=in;
            add(u,v);add(v,u);
            if(!vis[u]) vis[u]=1,n++;
            if(!vis[v]) vis[v]=1,n++;
        }
        for(i=1;i<=n;++i)
            if(!dfn[i])
                root=i,tarjan(i);
        memset(vis,0,sizeof(vis));
        for(i=1;i<=n;++i){
            if(!vis[i]&&!cut[i]){
                cnt=tot=0;num++;
                Dfs(i);
                if(!cnt) ans1+=2,ans2*=1ll*(tot-1)*tot/2;
                if(cnt==1) ans1++,ans2*=1ll*tot;
            }
        }
        printf("Case %d: %lld %lld\n",++cse,ans1,ans2);
    }
    
    return 0;
}