「一本通 3.6 例 2」矿场搭建

形式化题目

给定无向图 $G=(V,E)$ 。求最小的顶点集合 $X\subseteq V$ ，使得无论哪个顶点 $c$ 坍塌（从图中删去 $c$ ），其余每个顶点 $v$ 都能沿一条不经过 $c$ 的路径，到达 $X$ 中某个未坍塌的顶点；并求达到该最小值的 $X$ 的个数。图不保证连通；顶点全部由边引入，因此不存在孤立点。

正解

思路

从枚举出口改成刻画"咽喉"。 最朴素的想法是枚举出口集合 $X$ ：顶点数最多可达 1000， $2^{1000}$ 个子集根本不可行；即便给定一个 $X$ ，也要对每个坍塌点各查一遍连通性才能验证。瓶颈在于候选集合是指数级的，所以反过来问：哪些位置不得不放出口？

一个区域什么时候会与外界隔绝？当且仅当它进出的全部通道都经过被删掉的那个顶点——这正是割点的定义。于是把割点当作区域之间的公共咽喉，将图分解成点双连通分量（v-BCC）：极大的、内部任意删去一个顶点后仍然连通的子图（只有一条隧道连接的 $\{u,v\}$ 也算一个点双）。相邻的点双通过公共割点相连，每个割点至少属于两个点双。逐个点双 $B$ 按其包含的割点个数讨论：

点双内割点数	坍塌后的处境	最少出口	方案数
0（整个连通块就是一个点双）	出口所在的点一坍塌，块内再无出口	2	$\binom{\lvert B\rvert}{2}$
1（叶子点双）	唯一割点一坍塌，块内与外界隔绝	1	$\lvert B\rvert-1$
$\geqslant 2$	总能从另一个存活割点绕出去	0	1

割点数 0：连通块内部没有逃生咽喉。只放 1 个出口时，只要那个点坍塌出口就随之消失，其余点无处可去，所以至少要 2 个；任选两个顶点即可，共 $\binom{\lvert B\rvert}{2}$ 种选法。
割点数 1：记唯一割点为 $c$ 。 $c$ 坍塌时块内非割点与外界完全隔绝，所以块内必须有出口；而出口若建在 $c$ 上， $c$ 坍塌时出口会一起消失，因此出口只能建在 $\lvert B\rvert-1$ 个非割点上。选 1 个就够：无论哪个点坍塌，点双内部删一点仍连通，块内其余点总能走到这个出口。
割点数 $\geqslant 2$ ：块内任意点坍塌，幸存者都能经块内另一个割点走到别的点双，出口由外面的叶子点双提供，本块一个也不用建，方案乘 1。

这样放为什么一定够（充分性）。 把点双与割点交替连成块割树：每个连通块上，"点双—割点"的相邻关系构成一棵树，且叶子全是点双（割点至少属于两个点双，不可能成为叶子）。任取坍塌点 $c$ 与存活点 $v$ ：

若 $c$ 是割点：块割树删去 $c$ 后分裂成若干子树， $v$ 所在的子树必然仍含一个叶子点双（树的每个分支都有叶子）。该叶子的出口建在非割点上，一定不是 $c$ ，且与 $v$ 同处一棵子树；沿子树逐段走，每一段都落在某个点双内部，而点双删掉一个点后仍连通，因此能安全到达出口。
若 $c$ 不是割点：块割树结构不变，从 $v$ 所在的点双向外走到任意叶子点双即可；若出口恰好建在 $c$ 上，就改走另一个叶子点双（一棵树至少有两个叶子），无割点连通块则直接用它的第二个出口。

方案数为什么可以直接相乘。 非割点只属于唯一一个点双（割点的定义就是至少属于两个点双），所以不同点双挑选出口互不干涉：最少出口数取各块贡献之和，方案数取各块方案之积，既不重复也不遗漏。

样例 1 走查

下图是样例 1 的工地，红色顶点是全图唯一的割点 $1$ （顶点 $4$ 只连着它一条隧道）：

flowchart LR
  n1(("1")) --- n3(("3"))
  n1 --- n4(("4"))
  n3 --- n5(("5"))
  n1 --- n2(("2"))
  n2 --- n6(("6"))
  n1 --- n5
  n6 --- n3
  n1 --- n6
  n3 --- n2
  classDef cut fill:#ffd5d5,stroke:#d33,stroke-width:2px
  class n1 cut

删去顶点 $1$ 后 $4$ 变成孤岛，所以 $1$ 是割点；核心 $\{1,2,3,5,6\}$ 内部删任意一点仍然连通，它本身是一个点双，顶点 $4$ 与 $1$ 单独构成另一个点双——割点 $1$ 同时属于两者。按三分类公式逐块计算：

点双 $B$	包含的割点	割点数	贡献出口	贡献方案
$\{1,4\}$	$1$	1	1	$2-1=1$
$\{1,2,3,5,6\}$	$1$	1	1	$5-1=4$
合计	—	—	$2$	$1\times4=4$

表中每行是一个点双，"贡献出口/贡献方案"由三分类公式直接代入，合计即输出 Case 1: 2 4。它与题面给出的四组解完全对应： $\{1,4\}$ 块唯一的非割点是 $4$ ，所以出口必须含 $4$ ；核心块的出口从 $2,3,5,6$ 里任选一个，即 $(2,4),(3,4),(4,5),(4,6)$ 。

样例 2 是一棵树：每条隧道自成一个点双，割点为 $1,2,3$ ；恰含 1 个割点的是 $\{2,4\},\{2,5\},\{3,6\},\{3,7\}$ 四条边，各块唯一的非割点就是四个叶子，而 $\{1,2\},\{1,3\}$ 都含两个割点、贡献 0，于是 $1+1+1+1=4$ 个出口，方案 $1\times1\times1\times1=1$ ，输出 Case 2: 4 1。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 16:02
# update_at: 2026-09-30 16:02

import sys


def find_blocks(adj: list[list[tuple[int, int]]]) -> tuple[list[bool], list[set[int]]]:
    """Tarjan 求割点与点双连通分量（迭代版）：返回割点标记与各分量的顶点集合。"""
    n = len(adj)
    dfn = [0] * n          # DFS 编号，0 表示未访问
    low = [0] * n          # 子树经回边能到达的最小 DFS 编号
    cut = [False] * n      # 顶点是否为割点
    comps: list[set[int]] = []
    edge_stack: list[tuple[int, int]] = []      # 边栈：按序收集当前路径上的边
    clock = 0
    # DFS 栈三项：顶点、进入它的父边 id、下一条待检查的邻边位置（避免递归爆栈）
    dfs: list[list[int]] = []

    for root in range(n):
        if dfn[root]:
            continue
        clock += 1
        dfn[root] = low[root] = clock
        dfs.append([root, -1, 0])
        child_cnt = 0                          # 根的孩子数：大于 1 才是割点
        while dfs:
            u, parent_eid, i = dfs[-1]
            if i < len(adj[u]):
                dfs[-1][2] = i + 1
                v, eid = adj[u][i]
                if eid == parent_eid:          # 原路返回的树边不重复处理
                    continue
                if not dfn[v]:                 # 树边：向下展开
                    edge_stack.append((u, v))
                    clock += 1
                    dfn[v] = low[v] = clock
                    dfs.append([v, eid, 0])
                    if u == root:
                        child_cnt += 1
                elif dfn[v] < dfn[u]:          # 回边：只在编号大的一端入栈
                    edge_stack.append((u, v))
                    low[u] = min(low[u], dfn[v])
            else:
                dfs.pop()                      # u 全部邻边走完，向父节点回传 low
                if not dfs:
                    continue
                p = dfs[-1][0]
                low[p] = min(low[p], low[u])
                if low[u] >= dfn[p]:           # p 下方闭合出一个点双，弹出其边
                    block: set[int] = set()
                    while True:
                        a, b = edge_stack.pop()
                        block.add(a)
                        block.add(b)
                        if {a, b} == {u, p}:
                            break
                    comps.append(block)
                    if len(dfs) > 1:           # 根的割点判定在循环外按孩子数决定
                        cut[p] = True
        cut[root] = child_cnt > 1

    return cut, comps


def count_exits(cut: list[bool], comps: list[set[int]]) -> tuple[int, int]:
    """统计最少出口数与方案数：叶子分量出 1 个出口，无割点分量出 2 个。"""
    need = 0
    ways = 1
    for block in comps:
        size = len(block)
        cut_cnt = sum(cut[v] for v in block)
        if cut_cnt == 0:        # 整个连通块就是点双：任取两个顶点建出口
            need += 2
            ways *= size * (size - 1) // 2
        elif cut_cnt == 1:      # 叶子分量：出口必须建在非割点上，选一个即可
            need += 1
            ways *= size - 1
        # 含两个及以上割点的分量：割点坍塌后仍能绕行，无需出口
    return need, ways


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    case_no = 0

    for tunnel_cnt in data:               # 题目以 0 结尾
        if tunnel_cnt == 0:
            break
        edges = [(next(data), next(data)) for _ in range(tunnel_cnt)]

        # 顶点编号不连续，压缩成 0 基下标；边带 id 以便区分树边与父边的平行边
        verts = {v: i for i, v in enumerate({x for e in edges for x in e})}
        adj: list[list[tuple[int, int]]] = [[] for _ in verts]
        for eid, (a, b) in enumerate(edges):
            u, v = verts[a], verts[b]
            adj[u].append((v, eid))
            adj[v].append((u, eid))

        cut, comps = find_blocks(adj)
        need, ways = count_exits(cut, comps)
        case_no += 1
        out.append(f"Case {case_no}: {need} {ways}")

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 06:04
 * update_at: 2026-10-05 06:04
 */
#include <iostream>
#include <vector>
#include <map>
using namespace std;

const int MAXN = 1005; // 挖煤点数：隧道数 N <= 500，最多引入 2*N = 1000 个点
const int MAXM = 2015; // 无向隧道拆成两条有向边，最多 2*N+2
const int MAXB = 505;  // 点双个数不会超过隧道数 N

typedef long long ll;

int head[MAXN];   // 邻接表表头
int from_e[MAXM]; // 有向边起点，弹点双时用来统计顶点
int to_e[MAXM];   // 有向边终点
int nxt_e[MAXM];  // 同一顶点上的下一条边
int edge_cnt;     // 有向边计数，从 2 开始成对加入：i 与 i^1 互为反向边

int dfn[MAXN];    // DFS 编号，0 表示未访问
int low[MAXN];    // 子树经回边能到达的最小 DFS 编号
int is_cut[MAXN]; // 顶点是否为割点
int dfn_clock;

int edge_stack[MAXM]; // 边栈：Tarjan 过程中当前 DFS 路径上的边
int stack_top;

int block_visit[MAXN]; // block_visit[v] == visit_stamp 表示 v 已计入当前点双
int visit_stamp;

vector<int> block[MAXB]; // block[i] 保存第 i 个点双去重后的顶点集合
int block_cnt;

ll need;                  // 最少救援出口数
unsigned long long ways;  // 方案总数，题面保证答案小于 2^64，用无符号 64 位承接

// 加入一条无向边，拆成编号相邻的一对反向边：2 与 3、4 与 5 ……
void add_edge(int u, int v) {
    edge_cnt++;
    from_e[edge_cnt] = u;
    to_e[edge_cnt] = v;
    nxt_e[edge_cnt] = head[u];
    head[u] = edge_cnt;

    edge_cnt++;
    from_e[edge_cnt] = v;
    to_e[edge_cnt] = u;
    nxt_e[edge_cnt] = head[v];
    head[v] = edge_cnt;
}

// 从边栈弹出直到 tree_edge 为止的边，它们构成一个点双；顶点去重后存入 block[]。
void pop_block(int tree_edge) {
    visit_stamp++;
    block_cnt++;
    while (true) {
        int e = edge_stack[stack_top];
        stack_top--;
        int a = from_e[e];
        int b = to_e[e];
        if (block_visit[a] != visit_stamp) {
            block_visit[a] = visit_stamp;
            block[block_cnt].push_back(a);
        }
        if (block_visit[b] != visit_stamp) {
            block_visit[b] = visit_stamp;
            block[block_cnt].push_back(b);
        }
        if (e == tree_edge) break;
    }
}

// Tarjan 求割点与点双连通分量：u 为当前顶点，parent_edge 为进入 u 的边（0 表示根）。
void tarjan(int u, int parent_edge) {
    dfn_clock++;
    dfn[u] = dfn_clock;
    low[u] = dfn_clock;
    int child_cnt = 0; // 根的孩子数，大于 1 时根才是割点

    for (int i = head[u]; i != 0; i = nxt_e[i]) {
        int v = to_e[i];
        if (i == (parent_edge ^ 1)) continue; // 父边的反向边，直接跳过
        if (dfn[v] == 0) {
            child_cnt++;
            stack_top++;
            edge_stack[stack_top] = i;
            tarjan(v, i);
            if (low[v] < low[u]) low[u] = low[v];
            if (low[v] >= dfn[u]) {
                pop_block(i); // u 下方闭合出一个点双
                if (parent_edge != 0) is_cut[u] = 1; // 非根：有孩子无法绕过 u 即为割点
            }
        } else if (dfn[v] < dfn[u]) {
            // 回边：只从 DFS 编号大的一端入栈，避免同一条边入栈两次
            stack_top++;
            edge_stack[stack_top] = i;
            if (dfn[v] < low[u]) low[u] = dfn[v];
        }
    }
    if (parent_edge == 0) is_cut[u] = (child_cnt > 1);
}

// 按每个点双含割点的个数三分类，累加最少出口数、累乘方案数。
void calc_answer() {
    for (int b = 1; b <= block_cnt; b++) {
        ll size = block[b].size();
        ll cut_cnt = 0;
        for (ll j = 0; j < size; j++) {
            if (is_cut[block[b][j]]) cut_cnt++;
        }
        if (cut_cnt == 0) {
            // 整个连通块就是一个点双：出口所在的点坍塌后块内再无出口，至少要 2 个
            need += 2;
            ways *= size * (size - 1) / 2;
        } else if (cut_cnt == 1) {
            // 叶子点双：唯一割点坍塌后与外界隔绝，必须建出口，且只能建在非割点上
            need += 1;
            ways *= size - 1;
        }
        // 含两个及以上割点的点双：总能从另一个存活割点绕出去，不必建出口
    }
    for (int b = 1; b <= block_cnt; b++) {
        block[b].clear();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll tunnel_cnt;
    ll ea[MAXN]; // 当前组每条隧道的两个端点原始编号
    ll eb[MAXN];
    map<ll, int> vertex_id; // 原始挖煤点编号 -> 0 基压缩下标
    int case_no = 0;

    while (cin >> tunnel_cnt && tunnel_cnt != 0) {
        for (ll i = 1; i <= tunnel_cnt; i++) {
            cin >> ea[i] >> eb[i];
        }

        // 顶点编号不连续，压缩成 0 基下标；边从编号 2 开始成对加入
        vertex_id.clear();
        edge_cnt = 1;
        dfn_clock = 0;
        stack_top = 0;
        block_cnt = 0;
        // visit_stamp 不重置：block_visit 靠时间戳去重，必须保持单调递增
        need = 0;
        ways = 1;
        for (int i = 0; i < MAXN; i++) {
            head[i] = 0; // 加边前先清空表头，压缩下标在 0..2N-1 内
        }
        for (ll i = 1; i <= tunnel_cnt; i++) {
            if (vertex_id.find(ea[i]) == vertex_id.end()) {
                int id = vertex_id.size();
                vertex_id[ea[i]] = id;
            }
            if (vertex_id.find(eb[i]) == vertex_id.end()) {
                int id = vertex_id.size();
                vertex_id[eb[i]] = id;
            }
            add_edge(vertex_id[ea[i]], vertex_id[eb[i]]);
        }

        int n = vertex_id.size();
        for (int i = 0; i < n; i++) {
            dfn[i] = 0;
            low[i] = 0;
            is_cut[i] = 0;
        }

        for (int i = 0; i < n; i++) {
            if (dfn[i] == 0) tarjan(i, 0);
        }
        calc_answer();

        case_no++;
        cout << "Case " << case_no << ": " << need << " " << ways << "\n";
    }

    return 0;
}

复杂度

时间复杂度： $O(\lvert V\rvert+\lvert E\rvert)$ 。Tarjan 的显式 DFS 栈让每条边入栈、出栈各一次，分类统计再遍历一遍所有点双。 $N\leqslant 500$ 时每组实测约 $0.02\,\mathrm{s}$ ，远低于 1s 限制。
空间复杂度： $O(\lvert V\rvert+\lvert E\rvert)$ ，邻接表、dfn/low/cut 数组与两个栈，峰值约 15MB。
方案数可能接近 $2^{64}$ ，Python 的 int 是任意精度整数，直接承接。

总结

本题本质是"单点故障下的出口覆盖"：指数级枚举出口行不通，改用割点刻画"哪里必须放出口"。
把图分解成点双后按块内割点数三分类： $0 \to \big(2,\binom{\lvert B\rvert}{2}\big)$ ， $1 \to \big(1,\lvert B\rvert-1\big)$ ， $\geqslant 2 \to (0,1)$ 。
非割点独占一个点双，各块的选择互不影响，所以最少出口数按块求和、方案数按块连乘。
实现上用显式栈写 Tarjan，避开 Python 深递归的栈限制；顶点编号先压缩成 $0$ 基下标，邻接表携带边 id 以正确区分树边与回边。