题号 NC20099
名称 [HNOI2012]矿场搭建
来源 [HNOI2012]
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

作者：小熠小熠很不容易

题意

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

做法：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;
}

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目2月4日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴