[HNOI2012]矿场搭建

题意

给定一个无向图，问最少在几个点上设置出口，可以使得不管哪个点坍塌，其余所有点都可以与某个出口连通。求设置出口的数量及方案数。

做法：Tarjan，割点

前置芝士：割点

思路：

• 目前可公开情报：
  1.孤点：数量+1，方案数不变
  2.连通块无割点：数量+2，方案数
  
  3.连通块存在一个割点，数量+1，方案数
  (在一个强连通分量中只要建立1个)
  
  4.连通块存在两个及以上割点，数量不变，方案数不变
  

ps:这题题目并没有考虑有多个连通图，以及孤点的存在，应加强数据。
贴一组数据

1
2 3
6 
1 2
1 3
2 4
2 5
3 6
3 8
0

Case 1: 3 1
Case 2: 5 1

代码

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
#define debug(a) cout<<#a<<":"<<a<<"\n"
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=1010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

int n,m,cas;
vector<int> g[N];
int dfn[N],low[N],timetag; //dfn[u]:遍历到u的时间 low[u]:u通过有向边可回溯的最早次序(环中最小的dfn)
stack<int> s;
int dcc_cnt;
vector<int> dcc[N];
bool flag[N];

void init(){
    n=dcc_cnt=timetag=0;
    for(int i=1;i<=1000;i++) g[i].clear(),dcc[i].clear();
    mst(dfn,0);mst(low,0);mst(flag,0);
    s=stack<int>();
}

void tarjan(int u,int fa){
    dfn[u]=low[u]=++timetag;
    s.push(u);
    if(u==fa&&g[u].empty()){ //孤点
        dcc[++dcc_cnt].pb(u);
        return;
    }
    int cnt=0;
    for(auto v:g[u]){
        if(!dfn[v]){
            tarjan(v,u);
            low[u]=min(low[u],low[v]); //回溯 
            if(dfn[u]<=low[v]){
                cnt++;
                if(u!=fa||cnt>1) flag[u]=1;
                dcc[++dcc_cnt].pb(u);
                int y;
                do{
                    y=s.top();s.pop();
                    dcc[dcc_cnt].pb(y);
                }while(y!=v);
            }
        }
        else if(fa!=v){ //是不是在这个环中
            low[u]=min(low[u],dfn[v]);
        }
    }
}

void solve(){
    init();
    while(m--){
        int s,t;cin>>s>>t;
        g[s].push_back(t);
        g[t].push_back(s);
        n=max({n,s,t});
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i,i);
    }

    ll ans1=0,ans2=1;
    for(int i=1;i<=dcc_cnt;i++){
        int cnt=0;
        for(auto x:dcc[i]){
            if(flag[x]) cnt++;
        }
        if(!cnt){
            if(dcc[i].size()==1) ans1++; //孤点
            else ans1+=2,ans2*=dcc[i].size()*(dcc[i].size()-1)/2;
        }
        else if(cnt==1) ans1++,ans2*=dcc[i].size()-1;
    }
    cout<<"Case "<<++cas<<": "<<ans1<<" "<<ans2<<"\n";
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
//    int t;cin>>t;while(t--)
    while(cin>>m,m)solve();
    return 0;
}