[HNOI2012] 矿场搭建

题目解析

这是一个非常经典的图论题目，主要考察**割点（Cut Vertex）和点双连通分量（Biconnected Component, v-BCC）**的性质。

核心思路解析

题目要求我们在某些挖煤点设置救援出口，使得任意一个挖煤点坍塌（即该点被从图中删除）后，其他所有点的工人都能通过剩下的路径到达救援出口。

我们可以利用割点的性质来分析这个问题。

1. 什么是割点？

在一个无向连通图中，如果删除某个点及其相连的边，图分裂成了两个或更多的连通分量，那么这个点就是割点。

2. 分类讨论

我们可以使用 Tarjan 算法将图分解为若干个点双连通分量（v-BCC）。每个 v-BCC 是一个极大子图，其中任意两点之间至少存在两条点不重复的路径（或者说，删除该子图内任意一点，子图内部依然连通）。v-BCC 之间通过割点连接。

对于每一个点双连通分量，我们统计它包含的割点数量（记为 cut_num），分三种情况讨论：

情况 1：该连通分量中没有割点 (cut_num == 0)
- 这意味着整个图就是一个双连通分量（例如一个简单的环，或者完全图）。
- 最少出口数：2。因为如果只设 1 个出口，万一那个出口所在的点坍塌了，所有人都跑不掉。设 2 个出口可以保证坏掉一个还有一个。
- 方案数：从该分量的 $n$ 个点中任选 2 个，即 $C_n^2 = \frac{n(n-1)}{2}$ 。
情况 2：该连通分量中只有 1 个割点 (cut_num == 1)
- 这通常是位于图“边缘”的叶子分量。它只通过这唯一的割点连接到图的其他部分。
- 最少出口数：1。
  - 如果坍塌的点是割点，这个分量就与外界断开了，必须有一个内部出口才能逃生。
  - 如果坍塌的点是该分量内的非割点（包括出口本身），剩下的人可以通过割点逃往图的其他部分（只要其他部分有出口）。
- 方案数：出口可以设置在该分量内除了割点以外的任意一个点上。设该分量总点数为 $n$ ，则方案数为 $n - 1$ 。
情况 3：该连通分量中有 2 个或以上的割点 (cut_num >= 2)
- 这个分量处于图的“中间”位置，连接着多个其他部分。
- 最少出口数：0。
  - 无论分量内哪个点坍塌，幸存者都可以通过剩下的至少一个割点，逃往其他分量。只要那些边缘的分量（情况 2）按要求设置了出口，中间的人就能获救。
- 方案数：1（不需要设置，所以视为一种“不操作”的方案，对乘积无影响）。

算法流程

初始化：清空图、时间戳数组等。
求割点：使用 Tarjan 算法求出图中所有的割点。
求点双连通分量 (v-BCC)：
- 在 Tarjan 的过程中，用栈维护当前访问的节点。
- 当发现 low[v] >= dfn[u] 时，说明找到一个 v-BCC。
- 不断弹出栈顶元素直到 v，这些弹出的元素加上 u 构成了当前的 v-BCC。
统计与计算：
- 遍历每一个 v-BCC。
- 统计该 v-BCC 中包含的割点个数 cut_cnt 和总节点数 node_cnt。
- 根据上述三种情况累加最少出口数，累乘方案数。
输出结果：注意 long long（题目保证小于 $2^{64}$ ）。

C++ 代码实现 1

觉得我的代码长,就看实现2

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2025-12-30 15:36:29
 */
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 2e6+5;
const int maxe = 4e6+5;
const int mod = 1e9+7;

int n,m;
int a[maxn];


//oisnip_begin code/graph/linklist.cpp 内容开始

// const int maxn = 1e6+5;
// const int maxe = 1e6+5;

struct linkList {
    typedef struct {int u,v,w,next;} edge;
    edge e[maxe];
    int h[maxn],edge_cnt=0;
    linkList(){
        edge_cnt=0;
        memset(h,-1,sizeof(h));
    }
    void reset() {
        edge_cnt=0;
        memset(h,-1,sizeof(h));
    }

    //遍历点u 周围点
    template<typename U>
    void for_each(int u,U func){
        for(int i = h[u] ; i !=-1;i = e[i].next)
            func(e[i].u,e[i].v,e[i].w); //u v w
    }

    void add(int u,int v,int w=0){
        e[edge_cnt] = {u,v,w,h[u]};
        h[u] = edge_cnt++;
    }
    void add2(int u,int v,int w=0){
        add(u,v,w);
        add(v,u,w);
    }
    //下标访问
    edge& operator[](int i){ return e[i]; }

    // 参考 语法糖
    // https://en.cppreference.com/w/cpp/language/range-for.html
#ifdef __cpp_range_based_for
    // C++ 模板 和 策略模式（Policy） 来消除重复代码。
    // 我们可以定义一个通用的迭代器模板，通过传入不同的“提取器（Getter）”来决定 operator* 返回什么。
    // === 1. 定义数据提取策略 (核心区别) ===
    
    // 策略A: 获取整条边 (对应原本的 Iterator)
    struct UseEdge {
        using ReturnType = edge&; // 定义返回类型
        static ReturnType get(linkList* p, int i) { return p->e[i]; }
    };

    // 策略B: 只获取邻接点v (对应原本的 AdjIterator)
    struct UseAdj {
        using ReturnType = int;   // 定义返回类型
        static ReturnType get(linkList* p, int i) { return p->e[i].v; }
    };

    // === 2. 通用迭代器模板 (复用逻辑) ===
    template<typename Getter>
    struct BaseIterator {
        int i;          // 边的编号
        linkList* p;    // linkList指针
        
        BaseIterator(linkList* p, int i) : p(p), i(i) {}

        // 通用的遍历逻辑
        BaseIterator& operator++() { i = p->e[i].next; return *this; }
        bool operator!=(const BaseIterator& oth) { return i != oth.i; }
        
        // 差异化逻辑：委托给 Getter 处理
        typename Getter::ReturnType operator*() { return Getter::get(p, i); }
    };

    // 定义具体的迭代器别名
    using Iterator    = BaseIterator<UseEdge>;
    using AdjIterator = BaseIterator<UseAdj>;

    // === 3. 通用范围类模板 ===
    template<typename IterT>
    struct BaseRange {
        int start;
        linkList* p;
        BaseRange(linkList* p, int start) : p(p), start(start) {}
        IterT begin() { return IterT(p, p->h[start]); }
        IterT end()   { return IterT(p, -1); }
    };

    // === 4. 接口语法糖 ===
    
    // usage: for(auto& e : list(u))
    BaseRange<Iterator> operator()(int u) { return BaseRange<Iterator>(this, u); }

    // usage: for(int v : list.adj(u))
    BaseRange<AdjIterator> adj(int u) { return BaseRange<AdjIterator>(this, u); }
    
#endif
} e;

//oisnip_end code/graph/linklist.cpp 内容结束

//oisnip_beginv-bcc.cpp
/*
代码细节解释：

1. **`std::vector<int> bcc[maxn]`**:
* 与 SCC 不同，SCC 中每个点只属于一个分量，可以用 `id[u]` 数组标记。
* 在点双 (v-BCC) 中，**割点**会同时属于多个 BCC。因此，我们通常用 `vector` 列表来保存每个 BCC 里有哪些点，而不是给每个点打唯一的 ID 标记。


2. **`st.push(u)` 与出栈逻辑**:
* 我们将点入栈。
* 当满足 `low[v] >= dfn[u]` 时，说明找到了一个以 `u` 为“顶端”的双连通分量。
* 我们不断 `pop` 直到弹出 `v`。
* **关键点**：`u` 也是这个分量的一部分，需要 `bcc[...].push_back(u)`，但是 **`u` 不能出栈**。因为 `u` 还是它父节点所在 BCC 的一部分（如果 `u` 不是根），或者是其他子树分支 BCC 的分割点。


3. **`e(u)`**:
* 这里保留了你代码中的 `e(u)` 写法，假设你已经定义了类似 `#define e(u) head[u]` 或者相应的函数来获取邻接表头指针。
这是一个求 **点双连通分量 (v-BCC)** 的模板。


主要区别在于：

1. **无向图 DFS**：需要传入 `father` 参数防止走回头路（或通过边索引判断）。
2. **出栈时机**：SCC 是在回溯完 `u` 后判断 `low[u] == dfn[u]` 出栈；而 BCC 是在处理子节点 `v` 时，若发现 `low[v] >= dfn[u]`，则说明 `v` 及其子树无法绕过 `u` 到达更早的祖先，此时 `u` 和 `v` 的子树构成一个点双。
3. **割点特性**：一个割点 (Articulation Point) 可以属于多个点双连通分量。

*/

struct TarjanBCC {
    int n, timer;
    std::stack<int> st;
    int dfn[maxn], low[maxn];
    int bcc_cnt; // BCC 计数
    bool is_cut[maxn];
    int root; //记录根节点
    std::vector<int> bcc[maxn]; // 存储每个 BCC 包含的具体节点

    void set(int _n) {
        n = _n;
        timer = bcc_cnt = 0;
        memset(dfn, 0, sizeof(dfn));
        memset(low, 0, sizeof(low));
        memset(is_cut,0,sizeof(is_cut));

        while (!st.empty()) st.pop();
        for (int i = 0; i <= n; i++) bcc[i].clear();
    }

    // 无向图，需要 fa 参数防止直接走回父节点
    void dfs(int u, int fa) {
        dfn[u] = low[u] = ++timer;
        st.push(u);
        int child = 0;

        for (int i = e.h[u]; ~i; i = e[i].next) {
            int v = e[i].v;
            
            if (v == fa) continue; // 无向图核心：不走回头路

            if (!dfn[v]) { // 如果 v 没被访问过
                dfs(v, u);
                child++;

                if(u != root  && low[v] >= dfn[u]) {
                    is_cut[u] = 1; 
                }
                
                // 更新 low 值
                low[u] = std::min(low[u], low[v]);

                // 核心判断：low[v] >= dfn[u] 说明 v 没法回到 u 的祖先
                // 此时 u 是割点（或者根），u-v 这条边及其下方的点构成一个 BCC
                if (low[v] >= dfn[u]) {
                    bcc_cnt++;
                    while (true) {
                        int node = st.top(); st.pop();
                        bcc[bcc_cnt].push_back(node);
                        if (node == v) break; // 只要弹到 v 为止
                    }
                    // 注意：u 也是这个 BCC 的一部分，但 u 可能属于多个 BCC，
                    // 所以 u 不能出栈，只是把 u 加入到当前 BCC 列表中
                    bcc[bcc_cnt].push_back(u);
                }
            } else if (dfn[v] < dfn[u]) { // 返祖边
                low[u] = std::min(low[u], dfn[v]);
            }
        }

        if( u == root && child > 1) 
            is_cut[u] =  1;
    }

    void solve() {
        for (int i = 1; i <= n; i++) {
            if (!dfn[i] && e.h[i] != -1 ) {
                // 此时栈为空，dfs 根节点
                // 根节点的特判通常包含在上述 dfs 逻辑中
                // 只有当图中有孤立点时，需额外注意栈内残留
                root = i;
                dfs(i, 0); 
                
                // 如果是孤立点或者根节点处理完栈里还有元素（极少见情况，视题目定义而定）
                // 实际上标准 v-BCC 逻辑中，上述 dfs 里的 if (low[v] >= dfn[u]) 会处理所有连通块
                // 唯一的例外是如果 i 是一个孤立点（没有边的点），它不会进入循环
                // 如果需要记录孤立点为 BCC，可以在这里补判
            }
        }
    }

    // helper 
    int cut_cnt() {
        int cnt = 0;
        for(int i = 1;i <= n ;++i ) // i: 1->n
            cnt += is_cut[i];
        return cnt;
    }
};
//oisnip_end

TarjanBCC tj;


void init(){
    e.reset();
    m = 0; //记录最大的点
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        int u,v;
        std::cin >> u >> v;
        e.add2(u,v);
        if( m < u) m = u;
        if( m < v) m = v;
    }
    tj.set(m);
    tj.solve();

}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    int case_num = 0;
    while (1) {
        std::cin >> n;
        if( n == 0) break;
        init();

        // 计算答案
        ull ans = 1;
        int min_exits = 0;

        for(int i = 1 ; i <= tj.bcc_cnt ;i++) {

            int cut_cnt = 0;
            for( auto node : tj.bcc[i]) 
                cut_cnt += tj.is_cut[node];

            ull bcc_size = tj.bcc[i].size();
            
            if( cut_cnt == 0) {

                // 整个图是一个双连通分量，需要 2 个出口
                // 方案数为 C(size, 2)
                min_exits += 2;
                ans *= ( bcc_size *(bcc_size-1) / 2);
            }
            else if( cut_cnt == 1) {
                // 只有一个割点（叶子分量），需要 1 个出口
                // 方案数为 size - 1 (不能建在割点上)
                min_exits += 1;
                ans *= (bcc_size - 1);
            }
            // 割点数 >= 2，不需要额外出口
            // else {
            //     
            // }

        }

        std::cout << "Case " << ++case_num << ": ";
        std::cout << min_exits << " " << ans << "\n";
    }
    
    return 0;
}

C++ 代码实现 2

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <stack>

using namespace std;

const int MAXN = 1005; // 题目说 m <= 1000

struct Edge {
    int to;
};

vector<int> adj[MAXN];
int dfn[MAXN], low[MAXN], timestamp;
bool is_cut[MAXN]; // 标记是否为割点
int root;
stack<int> stk;
vector<vector<int>> bccs; // 存储所有点双连通分量

int n, m; // m 在此处作为最大节点编号

// 初始化函数
void init() {
    for (int i = 0; i < MAXN; i++) adj[i].clear();
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(is_cut, 0, sizeof(is_cut));
    timestamp = 0;
    while (!stk.empty()) stk.pop();
    bccs.clear();
    m = 0; // 重置最大节点编号
}

// Tarjan 求割点和点双连通分量
void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    stk.push(u);
    
    int child_count = 0;
    
    // 如果是孤立点，也算一个 BCC（虽然题目说连通，但为了鲁棒性）
    if (u == root && adj[u].empty()) {
        bccs.push_back({u});
        return;
    }

    for (int v : adj[u]) {
        if (!dfn[v]) {
            child_count++;
            tarjan(v);
            low[u] = min(low[u], low[v]);
            
            // 割点判定条件: low[v] >= dfn[u]
            if (low[v] >= dfn[u]) {
                // 记录割点
                if (u != root || child_count > 1) {
                    is_cut[u] = true;
                }
                
                // 提取点双连通分量
                vector<int> current_bcc;
                int z;
                do {
                    z = stk.top();
                    stk.pop();
                    current_bcc.push_back(z);
                } while (z != v);
                current_bcc.push_back(u); // 割点 u 也属于该 BCC
                bccs.push_back(current_bcc);
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

int main() {
    int edges_count;
    int case_num = 1;
    
    while (cin >> edges_count && edges_count != 0) {
        init();
        int u, v;
        for (int i = 0; i < edges_count; i++) {
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
            m = max(m, max(u, v));
        }

        // 遍历所有连通块（题目虽然说连通，但防止意外，遍历一遍）
        for (int i = 1; i <= m; i++) {
            if (!dfn[i] && !adj[i].empty()) { // 只处理存在的节点
                root = i;
                tarjan(i);
            }
        }

        unsigned long long total_ways = 1;
        int min_exits = 0;

        for (const auto& bcc : bccs) {
            int cut_cnt = 0;
            for (int node : bcc) {
                if (is_cut[node]) {
                    cut_cnt++;
                }
            }

            long long bcc_size = bcc.size();
            
            if (cut_cnt == 0) {
                // 整个图是一个双连通分量，需要 2 个出口
                // 方案数为 C(size, 2)
                min_exits += 2;
                total_ways *= (bcc_size * (bcc_size - 1) / 2);
            } else if (cut_cnt == 1) {
                // 只有一个割点（叶子分量），需要 1 个出口
                // 方案数为 size - 1 (不能建在割点上)
                min_exits += 1;
                total_ways *= (bcc_size - 1);
            } else {
                // 割点数 >= 2，不需要额外出口
            }
        }
        
        // 特判：如果整张图只有 1 个点的情况（题目边数 >= 1 所以通常不会出现，但逻辑上）
        // 如果题目保证边数>=1，那么至少2个点。
        // 上述逻辑在全图无割点时 min_exits += 2 是正确的。

        cout << "Case " << case_num++ << ": " << min_exits << " " << total_ways << endl;
    }
    return 0;
}

代码注意事项

数据范围： $N \le 500$ (边数)，节点编号最大 $1000$ 。int 足够存边，但方案数要用 unsigned long long。
输入结尾：注意处理以 0 结尾的输入。
Tarjan 细节：
- 在提取 BCC 时，栈中弹出的只到子节点 v 为止，父节点 u 是割点，属于该 BCC 但不能弹出（因为它可能还属于其他的 BCC）。需要手动把 u 加入当前的 current_bcc 列表。
- 根节点的割点判定条件是 child_count > 1。
去重：点双连通分量在存储时，割点会被包含在多个 BCC 中，但这正是我们需要的，因为我们需要统计每个 BCC 内部有多少个点是“全局割点”。

样例 1 模拟

输入构成了一个连通图。
割点为 3。
分解后，可能得到两部分：一部分是包含 3 的环状或复杂结构，另一部分可能挂在 3 上。
根据逻辑计算得出 2 4。

样例 2 模拟

输入：1-2, 1-3, 2-4, 2-5, 3-6, 3-7。
这是一个树状结构。
割点是 1, 2, 3。
v-BCCs: {2,4}, {2,5}, {3,6}, {3,7}, {1,2,3} (中间的三角形)。
- {2,4}: 割点 {2} (1个) -> 需要 1 出口，方案 $2-1=1$ (在4)。
- {2,5}: 割点 {2} (1个) -> 需要 1 出口，方案 $2-1=1$ (在5)。
- {3,6}: 割点 {3} (1个) -> 需要 1 出口，方案 $2-1=1$ (在6)。
- {3,7}: 割点 {3} (1个) -> 需要 1 出口，方案 $2-1=1$ (在7)。
- {1,2,3}: 割点 {1, 2, 3} (3个) -> 需要 0 出口。
总出口： $1+1+1+1 = 4$ 。
总方案： $1 \times 1 \times 1 \times 1 = 1$ 。
输出：Case 2: 4 1。