「一本通 3.6 练习 1」网络

形式化题目

给定 $N$ 个顶点、 $M$ 条边的无向连通图 $G=(V,E)$ 。称顶点 $u$ 为灾区：删去 $u$ 及其关联边后，剩下的顶点不再全部互相可达，即 $G-u$ 落在多于一个连通分量里；需要统计灾区的数量。图按行给出，每行 u v1 v2 ... 表示 $u$ 与 $v_1,v_2,\dots$ 相邻，每条边至少在某一行出现一次（可能只出现一次）。输入含多组数据，每组以单独一行 $0$ 结束，最后只剩一个 $0$ 。

样例第一组 $N=5$ ，只有一行 5 1 2 3 4，即边集 $(5,1),(5,2),(5,3),(5,4)$ 构成的星形图：删掉中心 5 后四片叶子互不相通，而删掉任一叶子其余四点仍然连通，所以只有 1 个灾区。

样例第二组 $N=6$ ，行 2 1 3 与 5 4 6 2 给出下图：

graph LR
    n1["1"] --- n2["2"]
    n2 --- n3["3"]
    n2 --- n5["5"]
    n5 --- n4["4"]
    n5 --- n6["6"]
    classDef cut fill:#ffd27f,stroke:#c00,stroke-width:2px;
    class n2,n5 cut;

它是一棵树，橙红色的 2 和 5 是灾区：删掉 2，剩下的点分成 $\{1\},\{3\},\{4,5,6\}$ 三块；删掉 5，分成 $\{4\},\{6\},\{1,2,3\}$ 三块；删掉任何一片叶子，其余五个点仍互相可达。所以输出 2。

正解

思路

朴素做法与它的瓶颈。 最直接的想法是逐点验证：对每个地点 $u$ ，把它从图里删掉，再从任意剩余点做一次 BFS/DFS，看能否到达所有剩余点——走不到就说明 $u$ 是灾区。这个做法正确，但要把整张图从头重扫 $N$ 遍，复杂度 $O(N(N+M))$ ；而删掉一个点只破坏与它相邻的局部，其余部分的连通信息全被丢掉重算。本题 $N<100$ ，这个量级下朴素做法其实也跑得动，但作为正式解法，应当给出与图规模同阶的线性算法。

观察：把"删掉 $u$ 后能否绕路"翻译成 DFS 树上的比较。 对图做一次 DFS，记每个点的访问序号 $dfn(u)$ ，以及它的子树内经回边能到达的最小序号 $low(u)$ ：

树边向下：孩子 $v$ 递归返回后，用 $low(v)$ 更新 $low(u)$ ；
回边（指向祖先的非树边）：直接用祖先的 $dfn$ 更新 $low(u)$ 。

于是" $u$ 的孩子子树能否绕开 $u$ 连到 $u$ 的祖先"就等于" $low$ 是否小于 $dfn(u)$ "，得到两条判据：

非根 $u$ ：存在孩子 $v$ 满足 $low(v)\geqslant dfn(u)$ ，说明 $v$ 的子树最远只能回到 $u$ 自己、回不到更早的祖先，删掉 $u$ 它必然自成一块， $u$ 是灾区；
DFS 树的根：根没有祖先，"回不到祖先"的说法失效，改成数子树——根有 $\geqslant 2$ 棵子树时删根至少剩两块，根是灾区；只有 1 棵子树时剩余点仍在同一棵树里，不是。

两条判据都不必真的删点：所有点的 $dfn$ 和 $low$ 在同一次 DFS 里同时算完。星形样例里，中心若被搜成根就走判据 2（4 棵子树），若从某片叶子开始搜则是非根点、走判据 1；样例二从 1 开始搜，根 1 只有 1 棵子树被判据 2 正确排除，2 和 5 由判据 1 命中。只写其中一条都会出错：少了根判据，从星形中心开始搜会漏掉唯一的灾区；少了非根判据，几乎所有中间点都判不出来。

样例二的一次 DFS（从 1 出发的一种访问顺序：邻点按编号从小到大；换一种合法顺序会改变 $dfn/low$ 的具体数值，但判据结论不变）：

点 $u$	$dfn$	$low$	DFS 树中的孩子	判定
1	1	1	2	根，只有 1 棵子树 → 不是
2	2	2	3、5	孩子 3： $low=3\geqslant dfn=2$ → 是
3	3	3	—	叶子 → 不是
5	4	4	4、6	孩子 4： $low=5\geqslant dfn=4$ → 是
4	5	5	—	叶子 → 不是
6	6	6	—	叶子 → 不是

这张表里每个点的 $low$ 都等于自己的 $dfn$ ，因为样例二是树、没有回边： $low$ 的候选只有自己的 $dfn$ 与孩子的 $low$ ，而孩子的 $dfn$ 都比自己大，取 $\min$ 后必然是自己。一般图里回边会把 $low$ 压回更早的祖先——比如一个环上每点都能绕回环的起点， $low$ 永远小于除起点外所有点的 $dfn$ ，所以环上一个灾区也没有。表中被标为"是"的 2 和 5 正是样例输出。

代码

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#!/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 15:56
# update_at: 2026-09-30 15:56

import sys


def count_disasters(adj: list[set[int]], n: int) -> int:
    """Tarjan 求割点数量：根看 DFS 子树数 ≥2，其余点看是否有孩子 low ≥ dfn。"""
    dfn = [0] * (n + 1)   # DFS 编号，0 表示尚未访问
    low = [0] * (n + 1)   # 子树内能到达的最小 DFS 编号
    is_cut = [False] * (n + 1)
    clock = 0             # DFS 时间戳，编号从 1 开始，0 留给"未访问"

    def dfs(u: int, parent: int) -> None:
        nonlocal clock
        clock += 1
        dfn[u] = low[u] = clock
        children = 0
        for v in adj[u]:
            if v == parent:          # 无向图唯一的父边不算回边
                continue
            if dfn[v]:
                low[u] = min(low[u], dfn[v])   # 回边：v 是祖先
            else:
                children += 1
                dfs(v, u)
                low[u] = min(low[u], low[v])
                # 子树 v 连不回 u 的祖先：删掉 u，v 那部分就断开了
                if parent and low[v] >= dfn[u]:
                    is_cut[u] = True
        if not parent and children > 1:        # 根断开后至少剩两棵互不相通的子树
            is_cut[u] = True

    for u in range(1, n + 1):        # 图保证连通；兜底处理万一的非连通块
        if not dfn[u]:
            dfs(u, 0)
    return sum(is_cut)


def solve() -> None:
    readline = sys.stdin.buffer.readline
    out: list[str] = []

    while True:
        line = readline()
        if not line:
            break
        n = int(line)
        if n == 0:                   # 最后一个块只有单独一个 0
            break

        adj: list[set[int]] = [set() for _ in range(n + 1)]
        while True:
            row = list(map(int, readline().split()))
            if row[0] == 0:          # 单独一行 0 结束本块
                break
            u = row[0]
            for v in row[1:]:        # 无向边：一条边至少在某一行出现，双向登记
                adj[u].add(v)
                adj[v].add(u)

        out.append(str(count_disasters(adj, n)))

    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/**
 * 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:05
 * update_at: 2026-10-05 06:05
 */

// 灾区即无向图的割点：一次 Tarjan DFS 维护 dfn/low，
// 非根点存在孩子 low >= dfn，或根在 DFS 树里有 >= 2 棵子树，即为灾区。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
const int MAXM = 20005; // N < 100，边数最多约 99*98/2，开两倍余量

typedef long long ll;

int n, m_cnt;          // m_cnt：当前块的边表长度
int head[MAXN];        // head[u]：u 的第一条边在边表中的编号，0 表示没有
int nxt[MAXM], to_[MAXM]; // 链式前向星：同起点的下一条边、这条边指向的点

int dfn[MAXN];       // dfn[u]：DFS 访问序号，0 表示未访问
int low[MAXN];       // low[u]：u 的子树内经回边能到达的最小 dfn
bool is_cut[MAXN];   // is_cut[u]：u 是否为灾区（割点）
int timer_cnt;       // DFS 时间戳，从 1 开始，0 留给"未访问"

// 加一条 u -> v 的有向边；无向边要正反各加一次。
void add_edge(int u, int v) {
    m_cnt++;
    to_[m_cnt] = v;
    nxt[m_cnt] = head[u];
    head[u] = m_cnt;
}

// Tarjan 求割点：father == 0 表示 u 是当前 DFS 树的根。
void dfs(int u, int father) {
    timer_cnt++;
    dfn[u] = low[u] = timer_cnt;
    int children = 0; // u 在 DFS 树中的子树数（只对根判据有用）

    for (int i = head[u]; i != 0; i = nxt[i]) {
        int v = to_[i];
        if (v == father) continue; // 无向图唯一的父边不算回边
        if (dfn[v] != 0) {
            // 回边：v 是祖先，用它的 dfn 压低 low[u]
            if (dfn[v] < low[u]) low[u] = dfn[v];
        } else {
            children++;
            dfs(v, u);
            if (low[v] < low[u]) low[u] = low[v];
            // 孩子 v 的子树绕不开 u 回到 u 的祖先：删掉 u 后 v 那块必然断开
            // 注意 father != 0：根的判据单独处理
            if (father != 0 && low[v] >= dfn[u]) is_cut[u] = true;
        }
    }

    // 根没有祖先，看子树数：>= 2 棵子树时删根至少剩两块
    if (father == 0 && children > 1) is_cut[u] = true;
}

// 处理一组数据：建图 + 求割点数量并输出。
void solve() {
    m_cnt = 0;
    timer_cnt = 0;
    for (int i = 1; i <= n; i++) {
        head[i] = 0;
        dfn[i] = 0;
        is_cut[i] = false;
    }

    // 每行 "u v1 v2 ..." 描述 u 的全部邻居；每条边至少在某一行出现一次，
    // 同一条边可能重复出现，这里直接重复登记，不影响割点判定。
    string line;
    while (getline(cin, line)) {
        istringstream iss(line);
        int first;
        if (!(iss >> first)) continue; // 跳过空行（含上一行 N 后残留的换行）
        if (first == 0) break;         // 单独一行 0 结束本块
        int v;
        while (iss >> v) { // 无向边：双向登记
            add_edge(first, v);
            add_edge(v, first);
        }
    }

    ll ans = 0; // 题目数据默认 ll
    for (int i = 1; i <= n; i++) {
        if (dfn[i] == 0) dfs(i, 0); // 图保证连通；逐点开搜兜底非连通
    }
    for (int i = 1; i <= n; i++) {
        if (is_cut[i]) ans++;
    }
    cout << ans << "\n";
}

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

    // 每组第一行是 N，最后的单独 0 结束输入；N 之后改用 getline 读整行邻居表
    while (cin >> n && n != 0) {
        solve();
    }

    return 0;
}

复杂度

时间复杂度： $O(N+M)$ ，每个点入栈一次、每条边被两个端点各扫一次；最外层对 $1..N$ 逐点开搜只是兜底，连通图里只进一次。
空间复杂度： $O(N+M)$ ，邻接表共 $2M$ 条记录，dfn / low / is_cut 各 $N+1$ 个槽位，递归栈最深 $N<100$ 。
本题 $N<100$ 、时限 1000 ms：真实数据 202 组、最大 $N=99$ 、 $M=245$ ，Python 实测约 0.03 s，无 TLE/MLE 风险。

总结

灾区就是无向图的割点：删点后剩余顶点不再全部互相可达。
朴素做法逐点删图、每次重扫是 $O(N(N+M))$ ；一次 Tarjan DFS 同时维护 $dfn/low$ ，把 $N$ 遍压成 1 遍，复杂度降到 $O(N+M)$ 。
两条判据必须配对使用：非根点看"是否存在孩子 $low\geqslant dfn$ "，根看"DFS 子树数 $\geqslant 2$ "。
输入每行只给单向邻居表，建图必须双向登记（set 顺带吸收重复出现的同一条边）；块终止符 $0$ 与从 1 起的顶点编号天然不冲突。

「一本通 3.6 练习 1」网络

目录

形式化题目

正解

思路

代码

复杂度

总结