解析
一道简单的tarjan题
题意：在无向图中找一些点，这些点组成的的点集记为\(V\) ，使得去掉任意一个点，剩下的每一个点都可以到达\(V\)中任意一个点，求点集\(V\)的大小的最小值及其方案数。
去掉一个点，很自然的联想到割点，那么考虑一下割点在不在备选集合中。
如图，显然可以看出，在割点上设立出口是劣的，因此我们永远不会在割点上设立出口。
既然不在割点上设立出口，那我们就把目光投向点双。
根据点双的定义，无论我们去掉哪一个点，剩下的点都可以相互到达。
因此我们只要在一个点双内设立两个出口就可以保证题目要求，方案数为\(\tbinom{n}{2}\)（证明很简单，分类讨论即可）
注意：刚才我们讨论的是一个点双，现在范围扩大一下
现在两个点双各被一个割点（加粗的黑点）相连了，每个点双内需要设立的出口数就变成了一个，Why？
-
假如去掉的点是割点
根据点双的定义，每个点双内部的点都能到达自己的出口。
-
假如去掉的点是点双内部的一个出口（这里假设为\(2\)）
虽然\(1\)，\(3\)到达不了\(2\)，但它们可以借助割点组成的“桥”来到达其他点。（这里的桥仅作比喻用）
如此，便可以得出：一个点双与一个割点相连只要设立一个出口，方案数为\(n\)
一个点双与两个及以上割点相连的情形是简单的
点集\(\{1,2,3,4\}\)组成的点双与两个割点相连，这意味着无论断哪个割点，这个点双内的剩余点都可以沿着其他割点走到别的点双内的出口。
有人一定要说：那我每个点双都与两个割点不就好了吗？
答案显然是不行
在只保留割点的情况下，所有的割点构成一棵无根树
根据割点的定义，每个割点都至少与一个点双相连
考虑度为\(1\)的节点
这个黑色圆圈代表的点双只要再连任意一条道割点的边，就会形成一个环，而这与割点的定义不符。
由此便可以写代码了，方案数按照乘法原理一个一个一个相乘就好了
代码
总算说完又臭又长的解析了，如果很急的话直接看代码就好了
注意割点不能选，算点双大小时不能把割点带上
code
// Problem: P3225 [HNOI2012]矿场搭建
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3225
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define db double
using namespace std;
const ll INF=1e18+7;
const db eps=1e-9;
const int MAXN=1e3+3;
ll n,m;
ll ans,ANS;
ll CNT,low[MAXN],dfn[MAXN],cnt;
vector<ll> graph[MAXN];
ll T,cut[MAXN],flag[MAXN],size,CUT;
void tarjan(int u,int fa){
low[u]=dfn[u]=++cnt;
int child=0;
for(auto v:graph[u]){
if(v==fa) continue;
if(!dfn[v]){
child++;
tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]&&fa!=u){
cut[u]=1;
}
}
else{
low[u]=min(low[u],dfn[v]);
}
}
if(u==fa&&child>=2){
cut[u]=1;
}
}
void clear(){
ans=1,ANS=CNT=cnt=0;
for(int i=1;i<=n;i++){
graph[i].clear();
}
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(flag,0,sizeof(flag));
memset(cut,0,sizeof(cut));
}
void dfs(int u){
flag[u]=CNT;
size++;
for(auto v:graph[u]){
if(flag[v]!=CNT&&cut[v]==1){
CUT++;
flag[v]=CNT;
}
if(flag[v]==0){
dfs(v);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
while(1){
clear();
T++;
cin>>m;
if(m==0){
break;
}
n=0;
for(int i=1;i<=m;i++){
ll u,v;
cin>>u>>v;
graph[u].push_back(v);
graph[v].push_back(u);
n=max(n,max(u,v));
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
tarjan(i,i);
}
}
for(int i=1;i<=n;i++){
if(!cut[i]&&!flag[i]){
size=CUT=0;
CNT++;
dfs(i);
if(CUT==0){
ANS+=2;
ans*=size*(size-1LL)/2LL;
}
if(CUT==1){
ANS+=1;
ans*=size;
}
}
}
cout<<"Case "<<T<<": "<<ANS<<" "<<ans<<"\n";
}
return 0;
}