题目链接
https://ac.nowcoder.com/acm/problem/20099
题意
一张无向图, 问至少设置几个点使得当删除一个点后其他所有点能到达设置点,以及方案数。
思路
点不能设置在割点, 所以对于断开割点形成的所有双连通分量中,进行分类讨论。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2000 + 50;
const int INF = 0x3f3f3f3f;
struct node{
int to, next;
} edge[maxn];
int tot, cnt;
int dfn[maxn], low[maxn];
int head[maxn];
bool is_true[maxn];
void add(int from, int to){
edge[++cnt].to = to;edge[cnt].next = head[from];head[from] = cnt;
}
void Tarjan(int u, int rt){
dfn[u] = low[u] = ++tot;
int rc = 0;
for(int i = head[u];i != -1;i = edge[i].next){
int v = edge[i].to;
if(!dfn[v]){
Tarjan(v, rt);
low[u] = min(low[u], low[v]);
if(low[v] >= dfn[u] && u != rt) is_true[u] = true;
if(u == rt) rc++;
}
low[u] = min(low[u], dfn[v]);
}
if(u == rt && rc >= 2) is_true[u] = true;
}
int vis[maxn], match[maxn];
void init(){
tot = cnt = 0;
memset(head, -1, sizeof(head));
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(is_true, false, sizeof(is_true));//割点
memset(vis, 0, sizeof(vis));//标记数组
memset(match, 0, sizeof(match));//标记割点的数组,防止多次访问割点计数。
}
int num, sz;
void dfs(int u, int rt){
if(is_true[u]){
if(match[u] != rt){
num++;
match[u] = rt;
}
return;
}
if(vis[u]) return;
vis[u] = 1;sz++;
for(int i = head[u];i != -1;i = edge[i].next){
int v = edge[i].to;
dfs(v, rt);
}
}
int main()
{
std::ios::sync_with_stdio(false);
int cas = 1;
int m;
while(cin >> m){
int n = 0, k = 0;
if(m == 0) break;
ll ans = 1;
init();
for(int i = 0;i < m;i++){
int u, v;
cin >> u >> v;
add(u, v); add(v, u);
n = max(n, u), n = max(n, v);
}
for(int i = 1;i <= n;i++) if(!dfn[i]) Tarjan(i, i);
for(int i = 1;i <= n;i++){
sz = 0, num = 0;
if(!vis[i] && !is_true[i]){
dfs(i, i);
if(num == 1){
k++;
ans = ans * sz;
}
else if(num == 0){
k = 2;
ans = 1LL * n * (n - 1) / 2;
}
}
}
cout << "Case " << cas++ << ": " << k << " " << ans << endl;
}
return 0;
}