专题 06 图论基础与遍历 · 复习强化

考点：图的组成（A1）。

（A1）考点：图 $G$ 由顶点集合 $V$ 和边集合 $E$ 组成，记作 $G = (V, E)$——边是顶点对，描述谁和谁相连（图的基本概念为大纲未明列、初赛高频内容）。

解析：先有顶点，再有"顶点与顶点之间的边"；图的全部信息就是"有哪些点、有哪些边"，与点的位置、边的长短无关。

排除法：选"一个数组和若干个链表"的人混淆了图的逻辑结构与存储结构（那是邻接表实现）；选"坐标和连线长度"的人被几何画法误导，图不关心位置与长度；选"一个起点和一个终点"的人把图和一条路径搞混了。

考点：有向与无向（A2）。

（A2）考点：每条边有方向（从出发端指向到达端）的图是有向图；add(1, 2) 只存了 $1 \to 2$，反方向未必有边。

解析：有向边是"单行道"：$1 \to 2$ 能走，不代表 $2 \to 1$ 能走；无向边才是"双行道"，存的时候要正反各加一次。

排除法：选"无向图，因为边没有长度"的人把"方向"和"长度"混为一谈——判据是方向不是长度；选"完全图"的人，完全图说的是"任意两点都有边"，与方向无关；选"连通图，因为 $1$ 能走到 $2$"的人，连通描述"能否互相到达"，描述不了边的方向。

考点：无向图的度（A3）。

（A3）考点：无向图中顶点的度＝与它相连的边数。顶点 $3$ 连着 $1$、$2$、$5$ 三条边，度是 $3$。

解析：数度就是"数有几条边碰到这个点"，一条边算一次，与边的另一端是谁无关。

排除法：选 $2$ 的人少数了一条边；选 $4$ 的人多数了一条；选 $6$ 的人把每条边按"两个端点"数了两遍——那是握手定理里"度数总和"的口径，不是单个点的度。

考点：入度与出度（A4）。

（A4）考点：有向图中，入度＝指向该点的边数，出度＝从该点出发的边数。$2 \to 4$、$3 \to 4$ 都指向 $4$，没有边从 $4$ 出发，所以顶点 $4$ 入度 $2$、出度 $0$。

解析：看箭头方向：箭头射进来记入度，箭头射出去记出度；$4$ 只出现在两条边的"终点"位置。

排除法：选"入度 $0$、出度 $2$"的人把箭头方向看反了；选"入度 $2$、出度 $2$"的人把入边又数了一遍出边；选"入度 $1$、出度 $1$"的人只数了一条入边。

考点：握手定理（A5）。

（A5）考点：无向图所有顶点度数之和＝边数的 $2$ 倍（每条边给两个端点各贡献 $1$ 度）。度数和 $3+2+2+1+3+3=14$，边数 $=14 \div 2 = 7$。（2024 年 CSP-J 单选真题考法）

解析：一条边 $(u,v)$ 让 $u$、$v$ 各加 $1$ 度，所以总和一定是偶数且恰为 $2m$；反过来 $m =$ 度数和 $\div 2$。

排除法：选 $14$ 的人忘了除以 $2$，把度数和直接当边数；选 $6$ 的人少数了一个 $3$；选 $8$ 的人多加了一度。

考点：有向图入度和等于出度和（A6）。

（A6）考点：有向图中每条边恰好给起点贡献 $1$ 出度、给终点贡献 $1$ 入度，所以入度总和＝出度总和＝边数。$8$ 条边则两者都是 $8$。（2025 年 CSP-J 单选真题考法）

解析：一条边"一出一入"成对出现，两条总和天然相等，都等于边数，与图是否连通无关。

排除法：选"$8$ 和 $16$"的人把出度又乘了 $2$；选"$4$ 和 $4$"的人把边数除以了 $2$（那是无向图度数和的口径）；选"取决于图是否连通"的人没抓住"每条边一一对应"的本质。

考点：自环与重边（A7）。

（A7）考点：无向图中自环给顶点贡献 $2$ 度（边的两个端点都是它自己）。$2$ 条普通边贡献 $2$ 度，加自环的 $2$ 度，共 $4$ 度。

解析：一条边贡献 $2$ 度的规则对自环同样适用，只是两端重合——不要按"一条边 $1$ 度"去数自环。

排除法：选 $3$ 的人把自环只算 $1$ 度；选 $2$ 的人干脆没算自环；选 $5$ 的人把自环算了 $3$ 度。

考点：无向完全图边数（A8）。

（A8）考点：$n$ 个顶点的无向完全图边数 $= \dfrac{n(n-1)}{2}$。$n=5$：$\dfrac{5 \times 4}{2} = 10$。

解析：每个顶点与其余 $4$ 个点各连一条边，$5$ 个点共 $5 \times 4 = 20$ 个"端"，每条边被数两遍，除以 $2$ 得 $10$——这正是握手定理的应用。

排除法：选 $5$ 的人忘了"每个点的边会被另一端再数一次"；选 $20$ 的人忘了除以 $2$；选 $25$ 的人按 $n^2$ 算成了"点对皆可双向"。

考点：简单路径（A9）。

（A9）考点：简单路径要求路径上的顶点不重复（除首尾相接成环的情形另算）。判断标准落在"顶点"上，不是边。

解析：路径是把边首尾相接串起来走；若中途绕回走过的点，就产生了"绕圈"，不再是简单路径。

排除法：选"没有重复的边"的人描述的是另一种更弱的限制，顶点仍可能重复（可以绕一个环）；选"必须经过所有顶点"的人把简单路径和哈密顿路径混了；选"长度必须为偶数"的人，路径长度没有奇偶限制。

考点：回路（A10）。

（A10）考点：起点与终点相同的路径称为回路（环）。$3 \to 4 \to 5 \to 3$ 用了 $3$ 条边、首尾同为 $3$，是长度为 $3$ 的回路。

解析：数回路长度＝数经过的边数；序列里 $3$ 出现两次（首、尾），边恰好三条。

排除法：选"长度为 $2$ 的简单路径"的人数错了边数，且首尾重合已不是路径；选"不是回路，因为它用了 $3$ 条边"的人以为回路只能有偶数条边——$3$ 条边首尾相接照样成环；选"两个独立的连通分量"的人，三点三边明明连成一片。

考点：连通分量计数（A11）。

（A11）考点：连通分量＝图中"极大的连通块"。边 $(1,2)$、$(2,3)$ 连成 $\{1,2,3\}$，$(5,6)$ 连成 $\{5,6\}$，剩下的 $4$、$7$ 各自是孤立点分量，共 $4$ 个。

解析：数分量的口诀：先找"有边相连"的块，再数孤立点——每个孤立点自成一个分量，最容易漏。

排除法：选 $3$ 的人漏数了孤立点；选 $1$ 的人以为图整体连通；选 $5$ 的人把 $\{1,2,3\}$ 拆成了两块。

考点：连通图至少 n 减 1 条边（A12）。

（A12）考点：$n$ 个顶点的无向图连通至少需要 $n-1$ 条边（树就是取到下界的连通图）。$10$ 个点至少 $9$ 条。（2020 年 CSP-J 单选真题考法）

解析：每加一条边最多把两个块并成一个，从 $10$ 个孤立块并成 $1$ 块至少要做 $9$ 次"合并"，所以至少 $9$ 条边。

排除法：选 $10$ 的人以为"点数＝边数"才连通，其实 $9$ 条摆成链即可；选 $11$、$12$ 的人多估了——边再多也是"至少"之上，不改变下界。

考点：删边成树（A13）。

（A13）考点：$n$ 个顶点的连通图要变成树（连通且恰 $n-1$ 条边），删掉的边数 $= m - (n-1) = m - n + 1$。$m=12$、$n=8$：$12 - 8 + 1 = 5$。（2021 年 CSP-J 单选真题考法）

解析：树是"边最少的连通图"（$n-1$ 条）；从 $12$ 条删到 $7$ 条，要删 $5$ 条，且只删"环上多余的边"就能保持连通。

排除法：选 $4$ 的人按 $m-n$ 算，少减了 $1$；选 $11$ 的人删到只剩 $1$ 条边，图不再连通；选 $7$ 的人把目标边数当成了删除数。

考点：矩阵加边代码（B1）。

（B1）考点：邻接矩阵用 $g[u][v] = 1$ 表示"$u$、$v$ 之间有直接边"。程序只赋值了 $(1,2)$、$(2,3)$ 两组，$g[1][3]$ 从未写过，数组初始化为全 $0$，输出 0。

解析：int g[10][10] = {} 把矩阵清零；判断"有没有直接边"只看一个格子，$1$ 能通过 $2$ 走到 $3$ 不影响 $g[1][3]$ 的值——连通≠相邻。

排除法：选 1 的人把"可达"当成了"相邻"，$1$ 到 $3$ 是两步的路径而非直接边；选 2 的人以为输出的是路径长度；选 -1 的人以为未赋值的元素是 $-1$，其实静态数组 {} 初始化是 $0$。

考点：无向矩阵对称性（B2）。

（B2）考点：无向图的邻接矩阵是对称矩阵：对任意 $u$、$v$ 都有 $g[u][v] = g[v][u]$——因为无向边 $(u,v)$ 同时给两个格子赋值。

解析：加边代码总是成对写 g[u][v] = g[v][u] = 1;，这正是"一条无向边、两个方向都能走"的体现。

排除法：选"只有对角线相等"的人没注意每对对称格子都相等；选"仅当图连通时才对称"的人，对称性来自"每条边成对赋值"，与连通无关；选"取决于加边顺序"的人——只要每条边都按标准写法成对赋值，顺序不影响对称性。

考点：矩阵空间 n 平方（B3）。

（B3）考点：邻接矩阵开 $n \times n$ 个 int（$4$ 字节），$n=1000$ 时 $1000 \times 1000 \times 4 = 4 \times 10^6$ 字节，约 $4$ MB。

解析：空间与边数无关、只与点数有关——哪怕只有 $10$ 条边也要开满一百万个格子，这是矩阵"以空间换查边速度"的代价。

排除法：选 $4$ KB 的人只算了一行（$1000 \times 4$ 字节）；选 $400$ KB 的人把字节数少算了一位；选 $40$ MB 的人多乘了一个 $10$。

考点：矩阵查边复杂度（B4）。

（B4）考点：邻接矩阵判断 $(u,v)$ 是否有边只需读 $g[u][v]$ 一个格子，时间 $O(1)$。

解析：行列号直接定位格子，一次内存访问出结果，这是邻接矩阵相对邻接表最大的优势。

排除法：选 $O(m)$ 的人按邻接表"扫邻居"的思维估；选 $O(\deg(u))$ 的人混淆了两种存储——扫完 $u$ 的所有邻居是邻接表的代价；选 $O(n)$ 的人把"扫一整行"当成了必要操作，其实按列号直达。

考点：有向连通矩阵非零下限（B5）。

（B5）考点：$N$ 个顶点的有向连通图至少要 $N-1$ 条边，每条边在矩阵里占一个非零格子（有向边只赋值一个方向），所以至少 $N-1$ 个非零元素。（2022 年 CSP-J 单选真题考法）

解析：连通的下界是"树形"结构（$N-1$ 条边都能用上）；这 $N-1$ 条有向边互不重合时非零格子最少。

排除法：选 $N$ 的人多算了一条；选 $N+1$ 的人以为还需要额外冗余边；选 $N^2$ 的人按满矩阵算——那是完全图才有的事，与"至少"不符。

考点：行和即度数（B6）。

（B6）考点：无向图邻接矩阵中，第 $u$ 行元素之和＝顶点 $u$ 的度。第 $2$ 行为 $1, 0, 1, 0, 0$，和为 $2$，即顶点 $2$ 的度是 $2$（与 $1$、$3$ 相连）。

解析：一行里的每个 $1$ 代表"一条与 $u$ 相连的边"，数 $1$ 就是数度；由对称性列和也等于度。

排除法：选 $1$ 的人只看到第一个 $1$；选 $3$ 的人把对角线或别的行的 $1$ 也数了进来；选 $4$ 的人数的是全矩阵 $1$ 的个数的一半之类，与单点度数无关。

考点：列和即入度（B7）。

（B7）考点：有向图矩阵中 $g[i][v] = 1$ 表示"有一条边从 $i$ 指向 $v$"。固定 $v$ 对行求和＝指向 $v$ 的边数＝入度。

解析：行号变化、列号固定，扫的正是"第 $v$ 列"；出度要反过来固定行扫一行。

排除法：选"出度"的人扫反了方向——出度是固定行、扫一行；选"度数"的人用了无向图口径，有向图要分入出；选"总边数"的人把所有格子都算上了。

考点：自环的矩阵表示（B8）。

（B8）考点：自环存在对角线上：$g[v][v] = 1$，只占一个格子，却给 $v$ 贡献 $2$ 度。用"行和"算度会少 $1$。

解析：行和把自环只数了 $1$ 次，而度的定义里自环算 $2$——所以带自环时行和＝度数 $- 1$，要补回来。

排除法：选"多 $1$"的人方向说反了；选"不变"的人忽略了对角线只占一格的事实；选"无法存"的人——对角线位置本来就是留给自环的，能存。

考点：带权矩阵（B9）。

（B9）考点：带权矩阵用 $g[u][v]$ 存边权，无边位置填 $0$（权为正的前提下）。读到 $g[u][v] = 0$ 只能断定"没有直接边"。

解析：$0$ 无法与"权为 $0$ 的边"区分，所以约定权为正时用 $0$ 兼表无边；带负权时应改用"无穷大"表示无边。

排除法：选"有一条权为 $0$ 的边"的人，题干已约定权均为正整数，$0$ 只能是无边的哨兵值；选"$u$ 到 $v$ 不可达"的人混淆了"没有直接边"与"没有路径"——$u$ 可能经其他点绕到 $v$；选"顶点 $u$ 不存在"的人，矩阵行不会因无边而失效。

考点：稀疏图选表不选矩阵（B10）。

（B10）考点：$n = 10^5$ 时矩阵要 $10^{10}$ 个格子（约 $40$ GB），内存不可行；边数 $m = 5 \times 10^4$ 远小于 $n^2$，是典型稀疏图，用邻接表 $O(n + m)$ 空间即可。

解析：存储选型的第一问是"空间开不开得下"：稠密小图用矩阵省事，大稀疏图必须上邻接表。

排除法：选"邻接矩阵，因为查边方便"的人没算空间账——查再快，开不出来都是空谈；选"二维 bool"的人只把内存除以 $32$，$10^{10}$ 个 bool 依然天文数字；选"各存一份"的人内存直接翻倍，更不可行。

考点：vector 邻接表结构（C1）。

（C1）考点：vector 邻接表给每个顶点挂一个动态数组，g[u] 存放 $u$ 的所有出边邻居，按 push_back 的先后顺序排列。

解析：add(u, v) 就是"把 $v$ 追加到 $u$ 的邻居名单末尾"——名单只记邻居编号，不记路径、不记权值。

排除法：选"$u$ 到其他点的路径"的人混淆了"直接邻居"和"多跳路径"，名单里只有一步可达的点；选"所有顶点的编号"的人——那是顶点表不是邻接表；选"坐标和权值"的人把图存储和题目数据搞混了。

考点：无向图加两条边（C2）。

（C2）考点：无向边 $(1,2)$ 用"只加单向"的 add 函数存时，必须调用两次：add(1, 2) 和 add(2, 1)，两个方向的邻接表各存一份。

解析：无向边的本质是"两个方向都能走"；只加 add(1, 2) 存出的是有向边，从 $2$ 出发根本看不到 $1$。

排除法：选 add(1, 1) 的人给顶点 $1$ 挂了个自环式的错误标记，方向问题没解决；选 add(2, 2) 的人给顶点 $2$ 挂了同样的错误标记；选"什么都不缺"的人把无向图当有向图存了，遍历会漏。

考点：表中元素总数 2m（C3）。

（C3）考点：无向图 $m$ 条边按标准写法（每条正反各加一次）存邻接表，全部 g[u] 的元素总数是 $2m$。$m = 6$ 时为 $12$。

解析：一条边贡献两个元素（起点表里一个、终点表里一个），与加边顺序无关；有向图才是每条边一个元素。

排除法：选 $6$ 的人忘了无向图每条边要存两次；选 $36$ 的人按 $m^2$ 算成了边两两组合；选"取决于加边顺序"的人——顺序只影响每个表内邻居的先后，不影响总数。

考点：遍历总复杂度 n 加 m（C4）。

（C4）考点：邻接表遍历：外层枚举 $n$ 个顶点、内层把每条表元素看一遍，无向图元素共 $2m$ 个，总时间 $O(n + m)$。

解析：每个顶点被外层碰一次、每条边（的两个方向元素）被内层碰一次，加起来就是 $n + 2m$，常数不影响量级。

排除法：选 $O(nm)$ 的人把"每个点要扫自己的邻居"误算成"每个点要扫所有边"；选 $O(n^2)$ 的人沿用了矩阵的复杂度；选 $O(m \log n)$ 的人凭空加了排序的对数因子。

考点：遍历邻居写法（C5）。

（C5）考点：for (int v : g[u]) 依次取出 $u$ 的全部出边邻居，顺序＝当年 push_back 的加边顺序（不是编号顺序）。

解析：vector 邻接表天然保持插入序——先加的边先被枚举，这也是同一张图用不同加边顺序会得到不同 DFS 序的原因。

排除法：选"按编号从小到大"的人把 vector 当有序容器了，除非手动排序，否则就是插入序；选"所有尚未访问的顶点"的人——循环里没有任何 vis 判断，取的全是邻居；选"祖先顶点"的人用了树的概念，图上没有天然的祖先。

考点：size 即度数（C6）。

（C6）考点：无向图标准加边下，g[u].size() ＝顶点 $u$ 的度。三条边 $(1,2)$、$(1,3)$、$(4,1)$ 各往 g[1] 里放一个元素，g[1].size() 是 $3$。

解析：每条与 $1$ 相连的边都让 $1$ 的表长加 $1$，表长就是度数——比矩阵行和更直接。

排除法：选 $2$ 的人漏了 $(4,1)$ 这条边；选 $6$ 的人把正反两次 push_back 都算进了 $1$ 的表里——反向元素进的是对方的表；选 $1$ 的人只数了一条边。

考点：表查边复杂度（C7）。

（C7）考点：邻接表判"$(u,v)$ 是否有边"要线性扫 g[u]，时间为 $O(\deg(u))$（$u$ 的邻居越多越慢）。

解析：表里没有"按编号直达"的下标机制，只能挨个看；最坏情况 $u$ 与所有点相连时退化为 $O(n)$，但按"度"描述最准确。

排除法：选 $O(1)$ 的人把矩阵的特性搬到了表上；选 $O(\log m)$ 的人以为表是有序可二分的；选 $O(n)$ 的人用的是最坏退化情形，不如按 $\deg(u)$ 刻画精确。

考点：链式前向星结构（C8）。

（C8）考点：链式前向星用三个数组存边：to[cnt] 是第 cnt 条边的终点，nxt[cnt] 是同起点的下一条边号，head[u] 是 $u$ 的第一条边号。

解析：它就是"数组模拟链表"版的邻接表——每条边记录"去哪"和"下一条在哪"，顺着 nxt 链就能枚举完 $u$ 的所有出边。

排除法：选"起点"的人——起点由 head[u] 的下标体现，不需要在边里存；选"权值"的人，这份代码根本没存权；选"上一次访问的顶点"的人把它当成遍历时的临时记录了，其实它是静态建图数据。

考点：头插法的逆序（C9）。

（C9）考点：add 把新边插到链头（nxt[cnt] = head[u]; head[u] = cnt;），所以从 head[1] 沿 nxt 枚举的顺序是后加的先出：4 3 2。

解析：依次加 $2$、$3$、$4$：加 $2$ 后链是 $2$；加 $3$ 后 $3$ 的下一条是 $2$；加 $4$ 后链头变 $4$——链变成了 $4 \to 3 \to 2$。

排除法：选 2 3 4 的人以为按插入顺序出链，头插恰恰相反；选 2 4 3、4 2 3的人都排错了链的指向，只能得到完整逆序链。

考点：head 初始化为负一（C10）。

（C10）考点：边号从 $1$ 开始，head[u] = -1 表示"$u$ 没有出边"——$0$ 会与合法边号冲突，$-1$ 才是安全的哨兵值。

解析：遍历写 for (int i = head[u]; i != -1; i = nxt[i])；若不初始化，全局数组默认的 $0$ 会被当成"第 $0$ 条边"读出垃圾数据（见 I 组排查题）。

排除法：选"$-1$ 会被自动跳过，不需要循环条件"的人——跳过靠的正是 i != -1 这个条件本身；选"表示内存未分配"的人把哨兵值和内存管理混了；选"只是习惯，用 $0$ 效果相同"的人没意识到 $0$ 是合法边号会撞车。

考点：边集数组（C11）。

（C11）考点：边集数组把每条边存成一个结构体（起点、终点、可选权值），按条躺在数组里——适合"逐条处理所有边"（统计、排序、枚举），不适合按顶点查邻居。

解析：三种存储各有所长：矩阵按"点对"索引、邻接表按"起点"索引、边集按"条"索引——按什么单位访问，就选什么存储。

排除法：选"频繁询问两点是否相邻"的人，边集要扫全表才能回答，矩阵才是 $O(1)$；选"快速枚举某点全部邻居"的人，那要扫全部 $m$ 条边过滤，邻接表直接给；选"只能存有向图"的人——无向边存成"两条有向边"即可。

考点：三种存储选择（C12）。

（C12）考点：$n = 500$ 时矩阵只要 $500^2 = 25$ 万个格子（约 $1$ MB），完全开得下；又需要频繁查任意两点是否相邻（$O(1)$），邻接矩阵是最佳选择。

解析：选存储看两件事：空间是否可行（$n \le$ 几千矩阵都行）、访问模式是什么（频繁按点对查→矩阵；按点枚举邻居→表；按条处理边→边集）。

排除法：选邻接表的人每次查边都要扫 g[u]，频繁查询会白白变慢；选链式前向星的人同样按邻居扫，且代码更绕；选边集数组的人每答一次"是否相邻"都要扫 $m$ 条边。

考点：递归框架与标记作用（D1）。

（D1）考点：DFS 递归框架里 vis[u] = true 标记"$u$ 已访问"，作用是防止沿环回到已访问的点造成无限递归与重复输出。

解析：图不一定是树，可能有环；没有标记，$1 \to 2 \to 3 \to 1$ 这样的环会让递归永远转下去（D15 专门验证）。

排除法：选"记录路径长度"的人，路径长度没存在 vis 里；选"给输出排序"的人，输出顺序由遍历本身决定；选"没有作用，删掉结果不变"的人只在树上侥幸成立，有环必炸。

考点：小图 DFS 序追踪（D2）。

（D2）考点：按插入序建表后 g[1] = [2,3]、g[2] = [1,4]、g[3] = [1,4]、g[4] = [2,3]。dfs(1)：访问 $1$，先走 $2$；$2$ 的邻居里 $4$ 未访问，走 $4$；$4$ 的邻居里 $3$ 未访问，走 $3$——访问序 1 2 4 3。

解析：DFS 一条路走到底再回头：$1 \to 2 \to 4 \to 3$，$3$ 的邻居全部已访问，逐层回溯结束。

排除法：选 1 2 3 4 的人按 BFS 层序走了；选 1 3 4 2 的人在 $1$ 处先走了后加的邻居 $3$（那是另一种合法 DFS 序，但与本题插入序不符）；选 1 4 2 3 的人让 $1$ 直接连到了 $4$——边 $(1,4)$ 根本不存在。

考点：遍历序取决于邻居枚举序（D3）。

（D3）考点：同一张图、同一 个起点，DFS 序仍可能不同：方式一插入序使 g[1] = [3,2]，先走 $3$ 得 1 3 4 2；方式二矩阵按编号升序枚举邻居，先走 $2$ 得 1 2 4 3。

解析：DFS 序由"每个点枚举邻居的顺序"唯一决定——表按插入序、矩阵按编号序，两套顺序自然导出两个访问序。

排除法：选两个 1 2 4 3 的人没注意方式一的插入序把 $3$ 排在了 $2$ 前面；选两个 1 3 4 2 的人把矩阵也当成插入序了；选含 1 2 3 4 的人混入了 BFS 层序。

考点：DFS 序不唯一的来源（D4）。

（D4）考点：连通图从固定起点 DFS，访问序不唯一——它由"每个顶点枚举邻居的顺序"决定：邻接表随加边顺序变，矩阵固定按编号升序。

解析：DFS 只规定"一条路走到底、回头换下一条"的骨架，不规定邻居先试谁；换一种存图或加边顺序，就可能得到另一个合法序。

排除法：选"结果本来随机"的人——不随机，给定枚举序后完全确定；选"起点不同"的人——题干已固定同一起点；选"顶点编号变化"的人——编号没变，变的是枚举顺序。

考点：可能最后遍历的点（D5）。

（D5）考点：枚举所有可能的邻居顺序，$b$、$c$、$e$ 都可能垫底（如 $a,c,d,e,b$、$a,b,d,e,c$、$a,b,d,c,e$），而 $d$ 永远不行——$e$ 只与 $d$ 相连，$e$ 要被访问必须先经过 $d$，所以 $d$ 不可能是最后一个。共 $3$ 个。（2021 年 CSP-J 单选真题考法）

解析：判"不可能最后"的抓手是割点式的必经性：$d$ 是通往 $e$ 的唯一跳板，垫底者必须没有"只能经它到达"的邻居挂着。

排除法：选 $2$ 的人漏了某个分支（三种角色不同的点都能垫底）；选 $4$ 的人没发现 $d$ 是必经点；选 $1$ 的人把不唯一性想得太保守。

考点：非连通图多次启动（D6）。

（D6）考点：非连通图一次 DFS 只能覆盖起点所在分量；主循环对每个未访问顶点补一次 dfs(u)，才能遍历全图。

解析：if (!vis[u]) 保证每个分量只在"第一个碰到的点"处启动一次；comp 顺便数出了分量个数。

排除法：选 dfs(u + 1) 的人跳过了可能的相邻点且会越界；选"只 vis[u] = true 不遍历"的人，同分量其他点永远没被访问，分量统计全错；选 comp = 0 的人把计数器清掉了。

考点：分量数与遍历方式无关（D7）。

（D7）考点：连通分量是图本身的性质；DFS 和 BFS 都能把一个分量完整走遍，统计出的分量个数必然相同。

解析：数分量的算法骨架＝"外层扫点 + 对未访问点启动一次遍历"——用什么遍历填空都行，结果只取决于图的连通结构。

排除法：选"只能 DFS"或"只能 BFS"的人把手段当成了目的；选"都要先排序"的人，排序与连通性无关。

考点：DFS 判连通（D8）。

（D8）考点：从 $1$ 出发 DFS 后若访问计数 cnt == n，说明 $n$ 个点全部可达，图连通；否则 cnt 就是 $1$ 所在分量的点数。

解析：一次 DFS 恰好覆盖起点所在连通分量的全部点——"访问到的点数"与"总点数"相等即连通。

排除法：选 cnt == 1 的人只访问到了起点（孤立点情形）；选 cnt == n - 1 的人把"树的边数 $n-1$"错记成了点数；选 cnt >= 2 的人，两个点的分量也满足，远不够判整图连通。

考点：DFS 判可达（D9）。

（D9）考点：dfs(u) 结束后 vis[v] 为真 ⟺ 存在从 $u$ 到 $v$ 的路径（可能经过很多中间点）。

解析：DFS 恰好把"从 $u$ 出发能走到的所有点"标完——这正是可达性的定义。

排除法：选"有直接边"的人混淆了边与路径（可达可能要绕好几跳）；选"最短路径就是 DFS 访问路径"的人——DFS 找到的路径常常绕远，最短要用 BFS；选"一步回到 $u$"的人把有向当无向、把路径当边了。

考点：显式栈压栈顺序（D10）。

（D10）考点：栈"后进先出"，想让邻居按 $1,2,3$ 的顺序被处理，必须逆序（$3,2,1$）压栈，让最先该处理的 $1$ 最后压、最先弹出。

解析：递归 DFS 与显式栈 DFS 要得到同一访问序，方向必须拧着来——栈会把你最后放的先拿出来。

排除法：选"正序压栈"的人访问序会整个反过来（先 $3$ 后 $2$ 后 $1$）；选"随便压"的人，顺序直接决定结果；选"只压一个邻居其余丢弃"的人，图的大部分点再也访问不到。

考点：链形图递归深度（D11）。

（D11）考点：链 $1-2-3-4-5$ 从 $1$ 递归 DFS 一路不回头，最深时 dfs(1)→dfs(2)→…→dfs(5) 同时挂 $5$ 层调用帧。

解析：递归深度＝走过的路径长；链形图是"最深的坑"，$n$ 个点的链深达 $n$——这也是 $10^5$ 长链爆栈的原因（见 I5）。

排除法：选 $4$ 的人少数了最外层那帧（或忘了起点自身）；选 $2$ 的人只算了某个局部；选 $6$ 的人多数了一层。

考点：邻接表 DFS 复杂度（D12）。

（D12）考点：邻接表 DFS：每个顶点进出一次、每条边（的两个方向元素）被扫一次，总时间 $O(n + m)$。

解析：复杂度来自"每点一次 + 每边一次"，这是邻接表对稀疏图的核心优势。

排除法：选 $O(n^2)$ 的人沿用了矩阵的账；选 $O(nm)$ 的人把"扫自己的邻居"误算成"扫所有边"；选 $O(m \log n)$ 的人多加了不存在的排序成本。

考点：邻接矩阵 DFS 复杂度（D13）。

（D13）考点：矩阵 DFS 访问每个顶点时都要扫一整行（$n$ 个格子）找邻居，$n$ 个点共 $O(n^2)$——与边数无关。

解析：矩阵把"找邻居"做成了全行扫描，哪怕一个邻居都没有也要扫完一行，这是它对稀疏图不友好的根本原因。

排除法：选 $O(n + m)$ 的人把表的账搬给了矩阵；选 $O(m^2)$ 的人跟边数较上了劲，矩阵的代价只看点数；选 $O(n)$ 的人漏算了每个点的整行扫描。

考点：DFS 生成树边数（D14）。

（D14）考点：DFS 过程中"每次沿它走到新顶点"的边（树边）恰有 $n - 1$ 条：除了起点，每个点都由唯一一条树边"领进门"。

解析：$n$ 个点被访问 $=$ 发生 $n-1$ 次"从已访问走到未访问"；其余的边都是回到已访问点的回边（非树边）。

排除法：选 $n$ 的人多数了起点；选 $m$ 的人把所有边都算成了树边，环上的边是走不到新点的；选 $n + 1$ 的人毫无依据地加一。

考点：删去标记行的后果（D15）。

（D15）考点：有环图上删掉 vis[u] = true 后，递归沿着 $1 \to 2 \to 3 \to 1 \to 2 \to \cdots$ 无限深入，最终栈溢出（运行错误）。

解析：没有标记，环上的点可以无限次重复进入；递归每层都压栈，深度无限增长直到崩溃——vis 正是防这个的（对照 D1）。

排除法：选"输出 1 2 3 正常结束"的人以为递归会自己停；选"正好两轮停止"的人，没有任何机制让它停；选"编译不通过"的人——这是运行期的逻辑错误，编译期查不出。