/*
题意:给定一个无向图,要求最少设置几个出口,使得任意点坍塌,其余点都可以走到出口。
①出口数>1,若只有一个出口,若坍塌的点是出口,那么将失败
②分别看每个连通块
[1]无割点 出口数:cnt >= 2
[2]有割点 缩点:
(1)每个割点单独作为一个点
(2)从每个V-DCC向其所包含的每一个割点连一条边
V-DCC度数为1,至少需要在分量内部(非割点)放一个出口,出口数:cnt >= 1
V-DCC度数大于1,无需设置出口 cnt >= 0
只要上述情况均取到等号,即可求出最小值,下面证明只要取到即可满足要求:
①如果坍塌的是某个割点;
割点至少会连接两个连通分量,而且缩完点之后必然是一棵树,将该割点删除,会形成至少两棵子树,
对于每一棵子树,子树上的每一个点都可以通过叶子节点上的出口逃出。因为叶子节点是度数为1的,
所以根据要求,肯定会有出口。
②如果坍塌的是某个度数为1的V-DCC的点,且不是割点;
由于是V-DCC所以,将坍塌的点删除后,该部分仍然连通,所以可以通过割点通往某个叶子节点,有出口
③如果坍塌的是某个度数为2的V-DCC的点,且不是割点;
至少会连接两个割点,以某一个割点为根节点,同样会形成至少两棵子树,对于度数为2的V-DCC,即使删掉一个点,
仍是连通的,同样可以通过叶子节点逃出。
综上所述:取到等号,即可取到最优解。
*/
#include <iostream>
#include <cstring>
#include <vector>
typedef unsigned long long ULL;
using namespace std;
const int N = 1010 , M = 510;
int e[M] , ne[M] , h[N] , idx;
int n , m , timestamp , top;
int low[N] , dfn[N];
int stk[N];
vector<int> dcc[N];//记录每一个双连通分量中有哪些点
int root , dcc_cnt;//
bool cut[N];
void add(int a, int b)
{
e[idx] = b , ne[idx] = h[a] , h[a] = idx++;
}
void tarjan(int u)
{
low[u] = dfn[u] = ++timestamp;
stk[++top] = u;
if(root == u && h[u] == -1)//是孤立点
{
dcc[++dcc_cnt].push_back(u);
return;
}
int cnt = 0;//记录使low[j] >= dfn[u]的j的数量
for(int i = h[u] ; ~i ; i = ne[i])
{
int j = e[i];
if(!dfn[j])
{
tarjan(j);
low[u] = min(low[u] , low[j]);
if(dfn[u] <= low[j])//如果j搜到的最小时间戳不小于u
{
cnt++;//分支数加一
if(u != root || cnt > 1) cut[u] = true;
//[1]如果x不是根节点,那么x是割点
//[2]如果x是根节点,至少要两个子节点j使low[j] >= dfn[u]
++dcc_cnt;
int y;
do{
y = stk[top--];
dcc[dcc_cnt].push_back(y);
}while(y != j);
dcc[dcc_cnt].push_back(u);
}
}
else low[u] = min(low[u] , dfn[j]);
}
}
int main()
{
int T = 1;
while(cin >> m , m)
{
for(int i = 1 ; i <= dcc_cnt ; i++) dcc[i].clear();
idx = n = timestamp = top = dcc_cnt = 0;
memset(h , -1 , sizeof h);
memset(dfn , 0 , sizeof dfn);
memset(cut , 0 , sizeof cut);
while(m--)
{
int a , b;
cin >> a >> b;
add(a , b) , add(b , a);
n = max(n , a) , n = max(n , b);
}
for(root = 1 ; root <= n ; root++)
if(!dfn[root])
tarjan(root);
int res = 0;
ULL num = 1;
for(int i = 1 ; i <= dcc_cnt ; i++)
{
int cnt = 0;//连通分量中割点数
for(int j = 0 ; j < (int)dcc[i].size() ; j++)
if(cut[dcc[i][j]])
cnt++;
if (cnt == 0)
{
if (dcc[i].size() > 1) res += 2, num *= dcc[i].size() * (dcc[i].size() - 1) / 2;
else res ++ ;
}
else if(cnt == 1) res ++ , num *= dcc[i].size() - 1;
}
printf("Case %d: %d %llu\n" , T++ , res , num);
}
return 0;
}
楼主你好,我想问一下这题为什么用不到bool in_stk[N] ?
啊这,我这题做太久了,你要不再看看y总视频😅,sorry
好吧,其实我也是做太久了回来复习的。。。