NC20099 [HNOI2012]矿场搭建

题目链接

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;
}