CSP-J 学习卷 L27 · 图论遍历与泛洪

规则：图的 DFS 必须用 vis 标记「到过的点」，防止重复访问与沿环无限递归；树天然无环、路径唯一，不需要。

考点：树与图的遍历差异。

解析：树上从根到任意节点的路径唯一，dfs 从父节点进入子节点后，子节点只会被父节点这一条路走到，所以不会重复。图的任意两点间可能有多条路径，还可能存在环：比如点 0 连着 1、2，而 1 也连着 2，那么 0 → 1 → 2 之后，2 再去看邻居时又会遇到已经走到的 0。没有 vis，0 → 1 → 0 → 1 会无限互调，最终栈溢出。

排除法：顶点多只是规模问题，树再多也不需要标记；与邻接表/邻接矩阵的实现方式无关；「图没有根」不准确，图可以指定遍历起点，标记的必要性来自环与多路径。

规则：vis 必须在「进入一个点、向它的邻居扩展之前」就标上；放到递归之后，邻居判断 !vis[v] 永远看不到已经走到的点。

考点：标记时机决定能否防重。

解析：dfs(0) 先不标记 0，扫描邻居 1 时发现 !vis[1] 成立，调 dfs(1)；dfs(1) 也不先标记，扫描邻居 0 时发现 !vis[0] 仍成立，又调 dfs(0)。两个函数互相调用，谁都不会先执行到 vis[u] = true 那行——因为每次都要先扫描完所有邻居。结果是无限递归，栈空间耗尽程序崩溃。

排除法：标记晚一步就失去了防重作用，不可能「正常访问各一次」或「只少一个点」；顺序颠倒的说法也建立在能正常终止上，实际根本不终止。

规则：图遍历的 vis 标记「这个点已经完成使命」，终身有效；搜索回溯的 used 标记「当前路径占用」，随路径进出需要恢复。

考点：遍历与回溯的标记语义区别（这是图论课与搜索课的分界点）。

解析：遍历要保证「每个点恰好访问一次」，所以标记过就永远不去了——恢复现场反而会让一个点被重复访问，在有环图上立刻死循环。回溯搜索要在状态空间里枚举全部排列，used[i] = true 表示「第 i 个元素正排在前缀里」，从这条分支退回时要把这个位置腾出来给同层其他分支用，所以必须恢复。判断标记要不要恢复，看它的含义是「终身的」还是「路径上的」。

排除法：与问题类别、有向无向、数组作用域都无关；唯一决定因素是标记语义。

规则：递归 DFS 每到一点先访问，再按邻接表顺序深入第一个未访问邻居，一条路走到底再回退。

考点：递归 DFS 的访问序手推。

解析：从 0 开始：输出 0，邻居是 1、2，先走 1。输出 1，邻居 3、4，先走 3（输出 3，无邻居返回）；再走 4（输出 4 返回）；1 的邻居走完返回 0；0 再走 2：输出 2，邻居 5，输出 5。整个顺序是 0 1 3 4 2 5。

排除法：0 2 5 1 3 4 是把邻接顺序倒过来先走 2；0 1 2 3 4 5 是顺序 BFS 的层序；0 1 3 4 5 2 把 2 和 5 的顺序放反了。

规则：栈是后进先出，最后压入的邻居最先弹出——所以访问序按「邻接表逆序」推进，与递归序不同。

考点：显式栈 DFS 与递归 DFS 的访问序差异。

解析：压 0（标记）→ 弹出访问 0，邻居 1、2 压栈（1 先压、2 后压，栈里 [1, 2]）→ 弹出 2 访问，邻居 5 压栈（栈 [1, 5]）→ 弹出 5 访问 → 弹出 1 访问，邻居 3、4 压栈（栈 [3, 4]）→ 弹出 4、3。顺序 0 2 5 1 4 3。递归版总是先深入第一个邻居，显式栈版先弹出最后压入的邻居。

排除法：0 1 3 4 2 5 是递归序；0 2 1 5 3 4 不是本程序的压栈顺序；0 1 2 3 4 5 是 BFS 层序。

规则：递归版的「下一个访问谁」由调用栈顶决定，等价于逐层只深入一个邻居；手写栈版把当前点所有未访问邻居一次性压入，弹出顺序与压入顺序相反。
考点：两种 DFS 实现的等价与差异。
解析：递归 DFS 里 dfs(0) 调用 dfs(1) 后要等 dfs(1) 整棵子树结束才轮到 2，所以先深入再回退——先输出 1、3、4。手写栈版在访问 0 时把 1、2 都压进栈，2 在栈顶先弹出，等于把邻接表顺序翻转——先输出 2、5。两种都是合法的 DFS（都符合「深度优先」精神），但访问序列不一定相同。若想让手写栈与递归序一致，可以逆序压栈。
排除法：两种实现都正确，只是弹出策略不同；与数据结构选型无关；不存在谁「没写对」。

规则：邻接表只扫描真实存在的边，总代价 $O(V+E)$；邻接矩阵每个点都要扫一整行（$V$ 格）判邻居，总代价 $O(V^2)$。

考点：两种存储的遍历复杂度。

解析：邻接表里每个点检查自己的邻居链表，每条边被看两次（无向图两个端点各一次），加上每个点的处理，合计 $O(V+E)$。邻接矩阵要判断 a[u][v] 是否为 1，必须把第 $u$ 行的 $V$ 格全扫一遍；$V$ 个点就是 $V \times V$，即 $O(V^2)$。所以稀疏图（$E$ 远小于 $V^2$）用邻接表遍历快得多。

排除法：矩阵遍历必然扫满 $V^2$ 格，不可能是 $O(V+E)$；邻接表不会退化到 $V^2$；说两者都是 $O(V^2)$ 是低估了邻接表的优势。

规则：邻接矩阵用「查表」代替「枚举」，查表的代价是必须扫整行才知道有哪些邻居。

考点：矩阵遍历复杂度来源。

解析：邻接表把邻居用链表直接列出来，扫描链表就是枚举邻居，代价正比于真实边数。邻接矩阵里邻居信息分散在 $V^2$ 个格子里，不扫完一整行就不知道点 u 连了谁。$V=10^4$ 时一行有 $10^4$ 格，扫 $10^4$ 行就是 $10^8$ 次判断——即使只有 $10^4$ 条边。这就是 $O(V^2)$ 的来源。

排除法：与数组访问快慢无关，纯属「必须扫整行」的结构代价；稀疏图完全满足遍历条件；矩阵不会自动跳过 0，0 也要逐个读。

规则：vis 天然免疫自环与重边——自环的邻居是自己（已标记），重边的重复目标也已标记。

考点：遍历对异常边的鲁棒性。

解析：dfs(u) 扫到自环 adj[u] 里的 u 时，vis[u] 已经为真，if (!vis[v]) 直接跳过。重边同理：v 第一次被访问后 vis[v] 为真，后面的重复边一律不触发。所以遍历代码不需要特殊处理自环和重边，vis 就够用了。

排除法：自环不会死循环——它连的就是自己，不会把遍历引到新地方；自环不可能「访问两次」因为第一次就标了；提前删边不是必须，vis 足够。

规则：带环图 DFS 也能正常结束——回边被 vis 挡掉，访问序由递归深入顺序决定。

考点：环对 DFS 访问序的影响。

解析：输出 0，邻居 1、2，先走 1。输出 1，邻居 0（已访问跳过）、2（未访问，走）、3（未访问）。先走 2：输出 2，邻居 0、1 都已访问，返回。再走 3：输出 3，邻居 1 已访问，返回。顺序 0 1 2 3。边 2-0 和 1-2（非树的回边）都被 vis 挡住。

排除法：0 1 3 2 是把 3 放 2 前面（邻接表里 2 在 3 前面）；0 2 1 3 是邻接表顺序反了；0 1 3 0 会重复访问 0，被 vis 挡住不可能发生。

规则：无向连通图 DFS 后，树边 = 顶点数 − 1；其余边都是回边（指向已访问的非父顶点）。

考点：DFS 对边的分类。

解析：DFS 递归树里 4 个点由 3 条边连成：0-1、1-2、1-3。剩下两条边 2-0、2-1 指向已经访问过的祖先，都是回边。一般规律：$V$ 个顶点的无向连通图，DFS 恰好用 $V-1$ 条树边连成生成树，$E-(V-1)$ 条边是回边（本例 $5-3=2$）。

排除法：树边不可能等于 4 或 5——生成树只保留 $V-1$ 条边；回边不可能只有 1 条，5 条边里 3 条是树边，余下 2 条。

规则：进函数先把 u 标记为已访问，再对每个未访问邻居递归 dfs(v)。

考点：DFS 模板骨架。

解析：第一空在输出之后、扫邻居之前，必须把当前点 u 标成 vis[u] = true——这样邻居回头访问 u 时会被 if (!vis[v]) 拦住。第二空对每个未访问的邻居 v 调用 dfs(v) 深入。注意第一空是标记 u（自己），不是 v。

排除法：填 dfs(u) 会无限递归；只标 v 不标 u 会让 u 自己永远可被再进；vis[u] = false 更是反向操作。

规则：vis 数组初值已经是「未访问」，标记必须写成 vis[u] = true；写成 false 就是什么都没做。

考点：标记的布尔方向。

解析：bool vis[N] = {} 初值全 false（未访问）。把 u 设成 false 不改变任何状态，if (!vis[v]) 对所有邻居恒成立，于是 dfs(0) → dfs(1) → dfs(0) → dfs(1) 无限互调，栈溢出。

排除法：「输出 0 1」「漏掉 1」「输出 1 0」都建立在会正常终止的假设上，实际程序无限递归根本不返回。

规则：BFS 从起点出发逐层扩展，第 $k$ 层里的点到起点恰好有长度为 $k$ 的路径，且不存在更短的路径。

考点：BFS 层数 = 无权图最短距离。

解析：BFS 先访问起点（第 0 层），再访问所有与起点直接相邻的点（第 1 层），再访问它们的未访问邻居（第 2 层）……点在第 $k$ 层出现，说明存在一条长度 $k$ 的路径；又因为 BFS 按层推进、第一次遇到就记录，更短的路径早就在更小的层里把它访问了，所以 $k$ 就是最短距离。

排除法：层数与度数无关；层数直接等于最短距离，不需要加 1；层数恰恰是路径长度的度量。

规则：BFS 按层推进，距离单调不减；DFS 深入优先，第一次撞到目标所在的路径不一定最短。

考点：BFS/DFS 对最短路的不同保证。

解析：BFS 队列里先弹出距离 0 的点、再距离 1 的点、再距离 2 的点……队列里的距离永远非递减。目标第一次被访问时，所有距离更小的层都已经处理完，不可能再有更短的路径。DFS 则是走一条路探到底，比如目标在 0 → 5 → 4 这条长路上，DFS 可能先走到它，而忽略 0 → 1 → 4 这条更短的——DFS 的「第一个」不等于「最短」。

排除法：不是快慢问题，DFS 即使枚举所有路径能求出最短，但那已不是「第一次访问即最短」；代码快慢无关；DFS 可以记录距离，记录的是当前路径长度而非最短。

规则：先到先标记——第一次入队时 dist 已是该点可达的最小值，后续发现它的路径只会更长或相同，重复入队没有意义。
考点：BFS 判重保证每点处理一次。
解析：点 v 第一次被某个邻居 u 发现时，dist[v] = dist[u] + 1 已经是能取得的最小层数（BFS 按层推进，任何更浅的路径都会更早发现 v）。之后从其他邻居再看到 v，dist[v] == -1 不再成立，continue 跳过——代码里 dist[v] == -1 这个判断就是「每个点只入队一次」的保证。这也是 BFS 复杂度 $O(V+E)$ 的来源。
排除法：与队列容量无关；「只能有一个父亲」是树的性质，图里一个点可以有多个邻居，但只有第一个算数；与奇偶无关。

规则：必须在「入队那一刻」就标记；出队才标记会让已入队但未出队的点看起来「没访问过」，被其他点再次入队。

考点：BFS 标记时机。

解析：0 入队，出队时标 0，把邻居 1 入队；1 出队时标 1，回头看邻居 0——0 已经被标过了，所以这次不重复。等等，这个例子里两个点，似乎没问题？关键在更大图：0 入队后还没出队，此时若另一个点 2 也连着 0，2 会再把它入队一次。以 0-1 加 2-1（1 同时连 0 和 2）为例：0、2 同时把 1 入队两次，第二次出队的 1 会再扫描一遍，把 0、2 又入队……队列不断膨胀。正确做法是在 q.push(v) 前就 vis[v] = true。

排除法：两个点时碰巧正常，三个点时已经出问题，不能说不正常不重；不会漏点也不会变 DFS，问题是重复入队。

规则：dist[v] == -1 表示未访问，dist[v] = dist[u] + 1 记录最短层数。

考点：BFS 距离表手推。

解析：dist[0]=0。第 1 层：0 的邻居 1、2 得 1。第 2 层：出队 1 时发现 3（dist[3]=2）；出队 2 时 3 已标记跳过、发现 4（dist[4]=2）。最终 0 1 1 2 2。

排除法：0 1 1 1 2 认为 3 在第 1 层（错，3 只能经 1 或 2 到达，都是第 2 层）；0 1 2 2 3 把 1、2 的层数算错；0 1 1 2 3 把 4 的层数算成 3（4 经 2 只需 2 步）。

规则：dist[4] = 2，最短路径为 0 → 2 → 4。

考点：BFS 距离查询。

解析：0 到 2 距离 1（直接边），2 到 4 距离 1（直接边），所以 0 → 2 → 4 长度 2。没有更短的路径（0 和 4 之间没有直接边）。

排除法：0 与 4 之间没有直接边，距离不可能是 1；3 是 0 到 3 的距离不是到 4；4 更不可能，图上最多相距 2。

规则：层数 = 到起点的最短距离；同层点最短距离相同。

考点：BFS 层的划分。

解析：0 在第 0 层。与 0 直接相邻的 1、2 在第 1 层。3 只能经 1 或 2 到达（距离 2），4 经 2 到达（距离 2），所以 3、4 在第 2 层。

排除法：3 不在第 1 层（它不直接连 0）；0 只在第 0 层；4 在第 2 层而不是第 3 层。

规则：BFS 用 dist[v] == -1 判未访问，用 dist[v] = dist[u] + 1 记录层数并充当标记。

考点：BFS 模板骨架。

解析：判重条件 dist[v] == -1（等价于未访问）；发现新点后先更新距离再入队。用 dist 充当 vis 是常见写法——距离表既是答案也是标记，省一个数组。

排除法：用 vis 数组也行但 dist 顺手记层数，填 dist[v] = dist[u] + 1 更完整；dist[v] > 0 会漏掉起点（距离 0）也判错未访问；adj[v].empty() 与距离无关。

规则：网格 = 隐式图——格子是顶点、相邻是边，网格 BFS 与邻接表 BFS 是同一个算法。

考点：显式图 vs 隐式图的统一。

解析：邻接表把边显式列出来；网格不用列——每个格子的「邻居」由方向数组当场算出来（上、下、左、右）。把每个格子当作顶点，网格就是一个顶点数 $n \times m$ 的图，BFS 在它上面求最短路与在显式图上完全一致。这就是「隐式图」的含义：边不存储，用时生成。

排除法：网格当然是图的一种表达；普通网格一样是隐式图；坐标与编号只是编码差异，算法同构。

规则：无向边等价于两条方向相反的有向边；有向图只沿出边扩展，「能到达」的范围受方向限制。

考点：有向图遍历的方向性。

解析：无向图里从 u 走到 v 也可以从 v 走到 u，遍历范围是「双向可达」的点。有向图里只有 u → v 时才能从 u 到 v，反之不一定。所以同一个起点在有向图上的可达集是「沿箭头方向能走到的点」，一般比把边当成无向时要小。

排除法：起点可以是任意点，不限于入度 0；有向图当然能用 BFS；距离与入度无关。

规则：有向 BFS 只沿出边走，0 → 1 → 3 → 4 是一步比一步长。

考点：有向图 BFS 距离。

解析：dist[0]=0；0 的出边到 1、2：dist[1]=1, dist[2]=1；1 的出边到 3：dist[3]=2；3 的出边到 4：dist[4]=3。所以 0 1 1 2 3。注意 4 只能经 3 到达，路径是 0→1→3→4 长度 3。

排除法：0 1 1 2 2 是把它当无向图（4 还能经 2）的结果；0 1 1 3 4 把 3 的层数算错；0 1 2 3 4 把 2 的层数算成 2。

规则：从单个起点 BFS 只能到达它所在的连通分量；孤立点的 dist 保持初值 -1。

考点：BFS 只覆盖可达部分。

解析：0 到 1、2 距离 1；3 经 1 或 2 距离 2；点 4 没有边、与 0 不连通，dist[4] 一直是 -1（初值）。-1 就是「不可达」的统一记号。

排除法：0 表示可达但距离 0（只有起点自己）；4 是点编号不是距离；3 的层数是 2 不是 1。

规则：dist 初值 -1（不可能出现的距离）充当「未访问」哨兵；距离非负说明已访问。

考点：一数两用的标记技巧。

解析：真实距离最小是 0（起点自己），-1 不可能是合法距离。所以「dist[v] == -1」等价于「v 还没被访问过」，「dist[v] != -1」等价于「已访问」。省掉 vis 数组，还能顺手把距离表当答案输出。

排除法：-1 不是合法距离，恰恰是哨兵；没有编译器补数组这回事；BFS 必须判重，只是判重方式并进了 dist。

规则：主循环每遇到一个未访问顶点，就意味着进入了一个新的连通分量，cnt++ 后 dfs 把它所在分量全部标记。

考点：连通分量计数原理。

解析：第一次遇到 0（未访问）→ 新分量，dfs(0) 把 0 所在分量全标完。之后主循环继续扫，分量内的其他点都已被标记、跳过；直到碰到下一个未访问的点，那一定是另一个分量里的点。所以「启动遍历的次数」= 分量个数。

排除法：cnt 不是点数（每个点不一定触发一次）；不是边数；不是递归深度。

规则：三条边各成一个连通分量，主循环分别在 0、2、4 处启动三次遍历。

考点：分量计数的手推。

解析：i=0 未访问 → cnt=1，dfs(0) 标记 0、1。i=1 已访问跳过。i=2 未访问 → cnt=2，标记 2、3。i=4 未访问 → cnt=3，标记 4、5。i=5 已访问跳过。cnt=3。

排除法：不是 1（图不连通）；不是 6（每个点不是独立分量，有边的点属于同一分量）；不是 2（三条边应得三个分量）。

规则：单次 dfs 只能沿边到达起点所在分量；其他分量的点没有任何边可达，必须靠主循环逐个点检查。

考点：主循环的覆盖作用。

解析：非连通图里，另一个分量的点与 0 之间没有任何路径。dfs(0) 把 0 所在分量标完后自然结束，永远到不了另一分量。主循环 for (int i = 0; i < n; i++) 的作用就是「兜底」：逐个点检查，发现没访问的就作为新分量起点。

排除法：不会死循环（遍历正常结束）；DFS 不会「自动跳」到无边可达的点；不会重复访问（vis 保证）。

规则：vis 是全局的「已处理」记录；不清空，主循环才能区分「已属于某分量」与「新分量」。

考点：vis 的全局语义。

解析：vis 记录的是「这个点已经归入某个分量、处理完毕」。若每开始一个新分量就清空，第一个分量的点在下一次 i 循环时又会显示「未访问」，再次 cnt++ 并重新遍历——同一个点被反复当成新分量，计数远大于真实分量数。保留标记正是「一数一次」的保证。

排除法：清空更慢且错；与数组大小无关；vis 声明位置不影响。

规则：遍历只能在图上沿着边走，分量之间无边，物理上跨不出去；「连通分量」的定义就是「彼此有边连通的极大点集」。
考点：分量定义与遍历可达性的关系。
解析：dfs/bfs 的每一步都要走到「当前点的邻居」才能前进。两个连通分量之间没有任何边：从分量 A 的 0 出发，dfs(0) 沿 0-1 标记 0、1 后结束，vis[2] 恒为假；bfs(0) 同理。跨到分量 B 需要一条「连接两分量的边」，而它不存在。这也正是需要主循环逐个起点兜底的原因。
排除法：DFS 会回溯、会遍历所有方向，但它需要边来连接；与编号大小无关；遍历没有额外深度限制（是图本身隔开了它们）。

规则：单次遍历覆盖的就是「整个连通分量」，连通 = 同分量 = 被同一次遍历覆盖。

考点：可达性判断。

解析：dfs(u) 会沿所有边把 u 所在分量的每个点都标记（前面已论证一次遍历=一个分量）。所以遍历结束后 vis[v] == true 当且仅当 v 与 u 在同一分量，即两点连通。这比在图上逐个找路径高效得多。

排除法：与访问时间无关；vis 标记的是整个分量不是一条路径；与编号无关。

规则：所有 4 个点都通过边连成一片（0、1、2 成三角形，2 再连 3），只有一个连通分量。

考点：连通性判断。

解析：从 0 出发 DFS：0 → 1、2 → 3，能走到全部 4 个点。主循环在 i=0 启动一次后，1、2、3 都已标记，cnt 不再增加。最终 cnt = 1。

排除法：2 是「图不连通」时才有；3、4 是把每个三角形顶点或每个点当分量。

规则：有向图可达性不对称：「u 能到 v」推不出「v 能到 u」。

考点：有向图的方向性。

解析：有向边 u → v 只允许从 u 到 v 的方向走。若图里没有 v → u 的边（或路径），从 v 出发就回不到 u。比如 0 → 1 的图，从 0 能到 1，从 1 不能到 0。这与无向图的「连通」概念不同——无向图的连通是双向的，有向图里「互相可达」是更强的性质（强连通）。

排除法：「图连通」对无向图成立，有向图要看方向；可达不是天然双向的；与是否有环无关（0→1→0 就有环且双向可达，但 0→1 单边无环则单向）。

规则：0 沿 0→1→3→4 和 0→2 能到全部点；2 没有出边，只能到达它自己。

考点：有向可达性计算。

解析：0 的出边到 1、2；1 到 3；3 到 4。所以从 0 可到 {0,1,2,3,4}。2 没有出边（2 后面没有箭头指向别的点），从 2 出发走一步都走不了，只能算 2 自己。

排除法：从 2 不可能到 3、4（没有 2 出发的边）；从 0 能到 2（直接边），所以 {0,1,3,4} 少了 2；{0,1,2} 少了 3、4。

规则：网格是隐式图——格子=顶点、四连通相邻=边；泛洪就是在这张隐式图上做 DFS/BFS。

考点：泛洪与图遍历的统一。

解析：泛洪从一个格子出发，把「所有连成一片的同类格子」全部标记。这正是从起点出发、沿「相邻」这条边扩展的遍历过程。网格的边不用存储，由方向数组当场算出，所以叫隐式图；泛洪的 DFS/BFS 实现与邻接表图上的遍历是同一个算法。

排除法：泛洪就是图遍历的一种形态；递归和 BFS 队列都常用；泛洪还能处理任意「顶点+邻居」定义的连通区域。

规则：四连通下，L 形三格连成一块，(2,3) 与 (4,4) 各自孤立，共 3 块。

考点：泛洪计数。

解析：(0,0)-(0,1) 左右相邻、(0,1)-(1,1) 上下相邻，三格在四连通下是一整块。(2,3) 周围四个方向（上、下、左、右）都不是陆地，(4,4) 同理，各成一块。总数 $1+1+1=3$。

排除法：1 是把所有陆地当一块；2 是少算一个孤立格；5 是把每个陆地格都当一块。

规则：每块泛洪时数格子数，取最大。

考点：面积（连通块大小）。

解析：左上块 (0,0)(0,1)(1,0) 共 3 格。右下块包含 6 格：(1,3)、(2,2)、(2,3)、(3,1)、(3,2)、(3,3)——它们两两相邻连成一片。最大值是 6。

排除法：3 是较小的那块；4、5 都不是任一块的真实大小。

规则：周长 = $4 \times 格子数 - 2 \times 相邻对数$。

考点：岛屿周长公式。

解析：3 个格子共 $3 \times 4 = 12$ 条边。相邻对数是 2（第 1 格-第 2 格、第 2 格-第 3 格），每对相邻各减 1 条边，共减 $2 \times 2 = 4$。周长 $12 - 4 = 8$。直观看：直线 1×3 的周长是上 3 + 下 3 + 左右各 1 = 8。

排除法：6 只减了每对相邻一条边（实际一对相邻要减 2，两个格各少 1）；10 少减了一对；12 是没减任何共享边。

规则：一条共享边由相邻两格各占一半——每个格子都损失 1 条外边，一对相邻共损失 2 条。

考点：周长公式的推导。

解析：把每个陆地格独立地数出 4 条边（总 4×格数）。相邻两个格子之间的边原本被数了两次（各自数了一次），而它并不是岛屿的外边界，所以两条都要去掉——每对相邻减 2。例如 2×2 全 1：$4 \times 4 = 16$ 条，相邻对数为 4（横 2 竖 2），$16 - 8 = 8$。

排除法：与四舍五入无关；减 1 会让周长多算；对角线相邻（八连通）不算共享边，只有四连通相邻才算。

规则：$3 \times 3$ 全 1：9 格共 36 条边，相邻对数 = 横 6 + 竖 6 = 12，周长 $36 - 24 = 12$。

考点：周长公式应用。

解析：$4 \times 9 = 36$。相邻对：每行 2 对 × 3 行 = 6 对横向，每列 2 对 × 3 列 = 6 对纵向，共 12 对。$36 - 2 \times 12 = 12$。直观：3×3 方块的边界是 $4 \times 3 = 12$。

排除法：8 是 2×2 的周长；10 是 1×3 与单格的混合错算；36 是把所有边都算了没减共享边。

规则：被包围的对象可能是「一整片 0」——需要判断的是这片 0 有没有任何一个格子能走到边界，反向泛洪恰好回答这个问题。

考点：被包围岛屿的判定思路。

解析：0 区域可以是一大片，比如 4×4 里中间 2×2 全是 0、四周被 1 围住。逐个格子判断「四周是不是 1」看不出 2×2 内部的 0 也被包围（它的邻居是 0）。正确语义是「这片 0 是否与边界连通」：从边界所有 0 出发泛洪，能走到的 0 都「没被包围」，剩下的才翻转。

排除法：不是性能问题，是语义问题；边界完全可能是 0（正是泛洪起点）；与泛洪方向无关。

规则：网格是 [1 1 1 1; 1 0 0 1; 1 1 0 1; 1 0 1 1]——边界上有一个 0（(3,1)），它和内部三个 0 不连通；内部 (1,1)(1,2)(2,2) 连成一片且被 1 围死，全部翻转。

考点：反向泛洪的结果。

解析：从边界出发：边界 0 只有 (3,1)（下标 3 行 1 列），它能访问的 0 只有它自己（四周是 1 或边界外），所以被「不翻转」保留的 0 只有 1 个。内部三个 0 连成一片但没有任何格子能到边界，全部翻转，共 3 个。

排除法：0 忽略了内部三个被围的 0；1 是边界那个不被翻的 0 的个数，题目问翻转个数；2 少算了一个。

规则：多源 BFS 把全部源点先入队（距离 0），再逐层扩散；每个格子第一次被访问时的层数就是到最近源的距离。

考点：多源 BFS 距离表。

解析：中心 (1,1) 距离 0。上下左右四个直接邻居距离 1。四个角 (0,0)(0,2)(2,0)(2,2) 距离 2（要绕过中心的两步）。所以表为 [[2,1,2],[1,0,1],[2,1,2]]。

排除法：[[1,1,1],...] 把角也算成距离 1；[[2,2,2],...] 把上下左右也算成 2；[[0,0,0],...] 没扩散。

规则：两个源同时入队，距离 0；中心 (1,1) 到两个源都是 2，其余点取较近源的距离。

考点：多源 BFS 取 min。

解析：(0,0) 和 (2,2) 距离 0。(0,1)、(1,0) 距离 1（近左上源）；(0,2)、(2,0) 距离 2（左上源要 2 步，右下源也 2 步）；(1,1) 到两源都是 2；(1,2)、(2,1) 距离 1（近右下源）。中心对称的 [[0,1,2],[1,2,1],[2,1,0]]。

排除法：[[0,1,2],[1,2,3],[2,3,0]] 把中心算成 3（其实到任意源都是 2）；[[0,1,2],[1,2,1],[2,3,0]] 把 (2,1) 算成 3；[[0,0,0],...] 没扩散。

规则：所有源点同时入队 = 想象一个虚拟超级源点，它与每个真实源连一条距离 0 的边；每个格子第一次被访问就是经过最近的源。

考点：多源 BFS 的等价模型。

解析：把多个源看成「都从同一个超级源出发、步数 0」，BFS 从超级源开始：第 0 层是所有源，第 1 层是源的所有邻居……某个格子第一次入队时，它所在的层数 = 从超级源到它的最短路径 = 经过某一个源的最短距离。由于 BFS 取「先到先得」，这个距离必然是所有源中最近的那个。

排除法：逐个源跑 N 遍是 $N$ 倍复杂度，多源一遍就够，不是「写法省略」；不存在「吞掉」；BFS 按队列顺序扩展，而队列层序保证公平。

规则：填充条件是与「起点原色」相同的格子才染色；8 个 g 与 r 不同色，不在填充范围内。

考点：图像填充的扩散条件。

解析：油漆桶先把起点原色 r 存下来，然后只把「同为 r 的四连通区域」改成 y。中心 r 的四个邻居全是 g，不同色不入队，所以只有中心自己变色。

排除法：填充会扩散，只是这里没有同色邻居；r 与 g 在四连通定义下相邻，但不同色不入队；与图像大小无关，全 g 也会扩散。

规则：起点原色 g，与它四连通的全 g 区域就是整张 2×2 图，全部染成 y。

考点：填充的连通块语义。

解析：从 (0,0) 出发，它的邻居 (0,1)、(1,0) 都是 g（同色）→ 染色并入队，再扩散到 (1,1)。最终四格都是 y。

排除法：填充染的是整个连通块不是单格；不只是右半或上半；起点 g 与目标 y 不同色，不需要特判。

规则：判定条件是「与起点原色同色」，不是「与当前格同色」；当前格染色后颜色已变，用它做参照就错了。

考点：填充算法的关键一步。

解析：填充过程中，已经染过的格子颜色变成 new_color。若用「邻居颜色 == 当前格颜色」来判断，已染色的格子是 new_color，它会带着不同色的邻居（还是原色的）一起染……判定条件自我污染，扩散不可控。正确做法是把起点原色固定为 prev，所有格子都拿自己的颜色和 prev 比。

排除法：不是少写代码的问题；与颜色种类无关；prev 是局部变量。

规则：入队即标记才能保证每个格子只入队一次；出队才标记时，尚未出队的格子看起来「没处理」，会被邻居再入队。
考点：泛洪与 BFS 的标记时机。
解析：网格是图，「入队即标记」是图上 BFS 的铁律。把 vis[nx][ny] = true 移到 q.push 之后（或出队时才标），两个相邻格子 a、b：a 入队未出队，b 看到 a「未标记」又把 a 入队……每个格子被反复入队，队列指数膨胀，一片大区域直接超时。正确写法 vis[nx][ny] = true 紧跟 q.push，让每个格子第一次被发现就「锁定」。
排除法：不是「慢一点」，是量级灾难；不会漏染（反而重复）；不同区域由颜色连通块决定，与标记时机无关。

规则：递归 DFS 每深入一个格子就占一个栈帧，满格连通时深度 400 万层爆栈；BFS 的队列在堆上、可增长，深度不受调用栈限制。

考点：递归深度 vs 显式数据结构。

解析：$2000 \times 2000 = 4 \times 10^6$ 个格子全连通时，递归 DFS 会沿着一条蛇形路径扎到底，调用深度约 400 万层。默认系统栈（通常几 MB，约几十万帧）撑不住，程序段错误崩溃。BFS 的队列最多同时存「一层边界」的格子，占用是 $O(周长)$ 量级，且队列内存来自堆，不存在调用栈限制。

排除法：代码长短无关；2000×2000 远在 int 范围内（400 万）；BFS 同样要标记，只是用 dist 或 vis。

规则：BFS（队列）或显式栈不占递归调用栈，深度可控，适合大网格。

考点：泛洪实现的工程选型。

解析：递归 DFS 的深度受系统栈限制，大网格（尤其满格连通）容易爆栈。BFS 队列或手写显式栈把「待处理」放在堆上，内存可控，是竞赛与工程的标准选择。数据小（如 $n \le 100$）时递归 DFS 也无妨。

排除法：递归 DFS 恰是要避免的；回溯是搜索不是泛洪；分治与连通区域染色无关。

规则：连通块由「边」定义；四连通只连上下左右（4 条边候选），八连通还连对角（8 条边候选），边集不同导致合并方式不同。

考点：连通定义与图边集。

解析：泛洪是「沿边扩展」的遍历。四连通时只有上下左右是边，两个对角格子不直接连通；八连通时对角也连边。所以同一条对角相邻的陆地，在四连通下是两块、八连通下是一块。这正说明「连通块」不是网格的固有属性，而是「边集」的产物。

排除法：与 DFS/BFS 无关；八连通块数 ≤ 四连通块数（边更多合并更多），不是「一定多」；网格大小相同。

规则：(0,0) 与 (1,1) 只在对角方向相邻——四连通不算边、八连通算边。

考点：对角相邻的差异。

解析：四连通只认上下左右，(0,0) 的邻居是 (0,1)、(1,0)，都没有陆地，所以 (0,0)、(1,1) 各成一块，共 2 块。八连通认对角，(0,0) 与 (1,1) 相邻，合成一块，共 1 块。

排除法：四连通 1 块或八连通 2 块都是方向反了；两块都 1 或都 2 忽略了两种连通的差别。

规则：二分图是「顶点可分两组，所有边跨组」的图；染色法把两组染成两种颜色，相邻异色等价于边只跨组。

考点：二分图定义与染色法的一致性。

解析：染色法从任意点开始染 0，邻居染 1，再给邻居的邻居染 0……如果能全程不冲突（任何边两端颜色不同），说明所有边都连接「0 色组」和「1 色组」，这就是二分图。

排除法：相邻异色是核心要求，不是同色；与度数奇偶无关；没有边的图当然也是二分图（平凡），但二分图不要求没边。

规则：偶数环可以二染色：0 色 0、2；1 色 1、3；边 2-3 两端 0 色对 1 色，不冲突。

考点：偶环是二分图。

解析：0 染 0；邻居 1、3 染 1；1 的邻居 2 染 0；3 的邻居 2 已染 0。最后检查边：0-1（0/1）、1-2（1/0）、2-3（0/1）、3-0（1/0）全部异色，成功。偶数环绕一圈后颜色刚好能接上。

排除法：1 和 2 染同色会导致边 1-2 冲突；4 环没有冲突；不是只有 0 能染。

规则：沿环走，每走一条边颜色翻转一次；走 $L$ 条边回到起点，颜色翻转 $L$ 次。$L$ 为奇数时起点颜色翻转成相反色，可起点还要和自己同色——矛盾。

考点：奇环 ⇔ 非二分图。

解析：假设沿环走一圈：0 色起点 → 走 1 条边到 1 色 → 走 2 条边回到 0 色 → ……每走一条边颜色翻转。3 条边绕回起点时颜色翻转为 1（与起点 0 相反），但绕回的「终点」就是起点，自己必须和自己同色。矛盾，所以染色必然在某个位置冲突。偶数环翻转偶数次回到原色，能闭合。

排除法：不是「染不了两种颜色」（0、1 两种够用，是奇环闭合矛盾）；与边数多少、度数无关。

规则：星形（树的一种）没有环，天然二分；三角形和 5 环都是奇环，非二分；「三角形 + 尾巴」仍含三角形，非二分。

考点：二分图识别。

解析：星形把中心染 0、叶子染 1，所有边（0-1、0-2）都异色，成功。三角形是 3 环（奇数环）非二分；5 环也是奇数环非二分；「三角形 + 尾巴」含 3 环，染色必然冲突。

排除法：三角形、5 环、含三角形的图都不是二分图；只有无奇环的星形是。

规则：边 1-2 的两个端点都被染成 1 色，违反相邻异色。

考点：染色冲突的发现。

解析：0 染 0，邻居 1、2 都要染 1。现在看边 1-2：1 是 1 色、2 是 1 色，同色冲突。这不是算法写错，而是图本身（三角形）无法二染色。

排除法：1、2 确实都是 1 色（它们只能与 0 异色）；不同色是不可能的；边 1-2 正是暴露矛盾的那条边。

规则：v == parent[u] 表示这条边是「刚走过来的树边」，属于正常回溯；只有指向「更早祖先（非父）」的已访问点才是回边，构成环。

考点：无向判环的父节点豁免。

解析：DFS 沿树边进入 u，u 回头看父节点时父已访问，但这条边本身就是到达 u 的边——把它算环会把所有树边都误判成环。真正的环是「u 有一条边指向某个祖先（不是父）」：比如三角形里 dfs(2) 时发现邻居 0 已访问且 0 不是父（父是 1），说明存在 2-0 回边，有环。

排除法：与编号无关；父节点当然可以被「访问到」（已经访问过）；父节点恰是最重要的邻居，只是要豁免。

规则：DFS 回溯到某个点发现「已访问的非父邻居」时报告有环。

考点：判环过程追踪。

解析：dfs(0) → dfs(1)（0 是 1 的父）→ dfs(2)（1 是 2 的父）。dfs(2) 扫描邻居：1（父，豁免）、0（已访问且不是父）→ 判定有环，返回 true。

排除法：三角形显然有环；DFS 能发现；算法对任何无向图适用。

规则：有向图的回边必须是「指向当前递归栈中祖先」的边（灰，color[v] == 1）；指向已完成点的边（黑，color[v] == 2）只是普通横叉边，不构成环。布尔标记无法区分「栈中」与「已完成」。
考点：三色 DFS 判环。
解析：color[u] = 1 表示 u 正在递归栈中；遇到 color[v] == 1 说明 v 还在栈里、存在「v 能到 u」的路径，u → v 把环闭合。遇到 color[v] == 2 说明 v 的子树已处理完，u → v 只是「又一条到达 v 的路」，构不成环。布尔 visited 只知道「访问过」，不知道是灰还是黑，所以必须用三色。
排除法：布尔标记在无向图（配合父节点豁免）够用，有向图才不够；与点数无关；三色不是省代码，是表达力需要。

规则：三色判环——指向「灰色（还在栈中）」的点才算环；指向「黑色（已处理完）」的点只是多了一条路径，不算环。

考点：三色标记对「回边」的精确定义。

解析：A 无环（一条链）。B：DFS 走 0（灰）→1（灰）→2（灰），2 的邻居 0 是灰色（在栈中），成环。C：DFS 走 0（灰）→1（灰）→2（灰）→ 2 无出边变黑 → 1 变黑 → 0 再扫描邻居 2，发现 2 是黑色（已处理完）——这不是回边，只是「又一条到 2 的路」，无环。关键就在：灰色代表「当前这条路径上」，黑色代表「已经探索完的别的路径」。

排除法：C 不是有环——指向黑色点不算环；「三者都有环」把「已访问的邻居」一律当环，正是布尔标记的误区；B 是有环的，说 B 无环错了。

规则：多条路径到达同一个点不算环；环要求「沿边能绕回自己」。

考点：DAG 与环的区别。

解析：DFS 走 0（灰）→1（灰）→3（灰）→ 3 无出边变黑 → 1 变黑 → 0 再走 2（灰）→2 看 3（已黑，不是灰）→ 2 变黑 → 0 变黑。全程没有任何「灰点指向灰点」，无环。3 被 1→3、2→3 两条路到达只是入度为 2，不构成环。

排除法：多条路径 ≠ 环；「无法判断」不对；边数 4 不代表有环。

规则：递归先进入祖先再进入后代，且先离开后代再离开祖先——所以祖先的 [in, out] 区间完整包住后代的区间。
考点：时间戳的括号嵌套性质。
解析：dfs(u) 进入（记 in[u]）→ 递归处理子树 → 返回（记 out[u]）。若 v 在 u 的子树里，v 的进入、离开都发生在 u 的进入、离开之间，即 in[u] <= in[v] 且 out[v] <= out[u]，u 的区间包含 v 的区间。两个条件缺一不可：只满足 in[u] < in[v] 不能保证（可能 v 在另一条分支上）。
排除法：单个条件不够；与编号无关。

规则：先进入 0（1）→1（2）→3（3、离开 4）→1 离开（5）→2（6）→4（7、离开 8）→5（9、离开 10）→2 离开（11）→0 离开（12）。

考点：时间戳手推。

解析：完整序列：in[0]=1；in[1]=2；in[3]=3、out[3]=4；out[1]=5；in[2]=6；in[4]=7、out[4]=8；in[5]=9、out[5]=10；out[2]=11；out[0]=12。所以 in[1]=2, out[1]=5, in[3]=3, out[3]=4, in[2]=6, out[2]=11。

排除法：in[1]=3 错（1 在 3 之前进入）；in[0]=0 错（第一个进入是 1）；out[3]=3 小于 in[3] 不可能。

规则：in[1]=2 <= in[3]=3 且 out[3]=4 <= out[1]=5，区间包含 → 1 是 3 的祖先；in[2]=6 > in[3]=3，区间不包含 → 2 不是。

考点：祖先判定的区间法。

解析：1 的区间 [2,5] 包住 3 的 [3,4]，1 是 3 的祖先（3 在 1 的子树里）。2 的区间 [6,11] 与 3 的 [3,4] 完全不相交——3 是 1 的分支，2 是另一棵子树，2 当然不是 3 的祖先。

排除法：2 与 3 在不同子树，不是祖先；两区间包含关系明确，可以判断。

规则：邻接矩阵空间 $O(V^2)$，$V=10^4$ 时 $10^8$ 格 ≈ 100MB（bool 型），且遍历每行扫 $V$ 格。

考点：邻接矩阵的空间复杂度。

解析：$n = 10^4$，矩阵 $n^2 = 10^8$ 个格子，每个 bool 至少 1 字节，约 100MB，接近内存上限；遍历时每点扫一行又是 $10^8$ 次判断。稀疏图（如 $m=10^4$ 条边）用邻接表只要 $2m$ 个边记录 + $n$ 个表头，约几万单位，遍历 $O(n+m)$。

排除法：矩阵能存稀疏图只是浪费；不会死循环；哈希表不是必须。

规则：递归每层调用占一个系统栈帧；显式栈是自己在堆上维护的数据结构，不受系统栈容量限制。
考点：递归 vs 显式栈的容量差异。
解析：递归函数 dfs 每深入一层，系统就在调用栈上压一个帧；默认栈几 MB，深到几十万层就段错误。显式栈把「待处理」的节点放在自己管理的 vector 里，st.push_back/st.pop_back 只动自己的容器，容量只受堆内存限制，链式图再深也装得下。注意两段代码的判重逻辑相同，都要 vis 防重。
排除法：访问次数相同；速度可能略慢（手写开销）；显式栈同样需要 vis 防重。

规则：dist 初值 0 让「未访问」哨兵失效——dist[v] == -1 恒假，BFS 一步都扩展不出去。

考点：-1 哨兵的初值必须正确。

解析：初值 0 意味着每个点「看起来已访问且距离 0」。从起点出队后扫描邻居，dist[v] == -1 对谁都为假，没有点入队，队列立即空。输出只有起点是 0，其余全是 0（初值）。正确初值应该是 -1：未访问的点判重生效，距离才一个个算出来。

排除法：不是正常——距离全是错的；不会死循环（队列很快空）；不是多 1，是根本算不出来。

规则：按邻接表顺序 DFS：0 → 1 → 3 → 返回 → 2 → 4。

考点：阅读 DFS 程序。

解析：adj[0] 是 [1, 2]，先走 1；adj[1] 是 [0, 3]，0 已访问，走 3（无邻居）；返回 1、返回 0，再走 2；adj[2] 是 [0, 4]，走 4。顺序 0 1 3 2 4。

排除法：0 2 4 1 3 需要 adj[0] 先 2 后 1；0 1 2 3 4 是 BFS 层序；0 1 3 4 2 把 2、4 顺序搞反。

规则：DFS/BFS 的访问序是「遍历树」的产物；先还原这棵树，再沿树模拟递归/队列，顺序自然正确。

考点：读图遍历程序的方法论。

解析：递归 DFS 的「下一个访问谁」由当前点在遍历树里往哪走决定——每个点只会因为第一次被访问的那条边进入树。把这条边画出来，整棵树的父子关系明确，那么从根出发「先深入左子树再回退」的序列就是答案。这个方法把抽象的递归变成看得见的树，是最可靠的读程序手段。

排除法：树不会自动排序，是它提供了推演依据；遍历树是生成树不是图本身；与程序能否运行无关。

规则：矩阵按列号从小到大找邻居，等价于「邻接表顺序 = 顶点编号升序」。

考点：邻接矩阵 DFS。

解析：从 0：扫第 0 行，v=1 是邻居（先于 v=2），走 1；从 1：扫第 1 行，v=0 已访问、v=3 是邻居，走 3；从 3：唯一邻居 1 已访问。返回 1、0，再扫 0 行 v=2，走 2。顺序 0 1 3 2。

排除法：0 2 1 3 是把 2 放在 1 前面（列序是 1 在前）；0 1 2 3 是 BFS；0 2 3 1 完全乱序。

规则：邻接表顺序决定了「先深入谁」；乙的 adj[0] 是 {3, 2, 1}，按此顺序深入。

考点：加边顺序与遍历序的对应。

解析：乙先插 3、再 2、再 1，adj[0] = {3, 2, 1}。DFS：0 → 3（无邻居）→ 返回 → 2 → 返回 → 1。输出 0 3 2 1。同一张图，遍历序完全镜像。

排除法：0 3 1 2 把 2、1 顺序搞反（链表顺序是 3 在前）；0 1 2 3 是甲的；0 2 1 3 不符合任何插入顺序。

规则：无判重 BFS 在环上把已访问点反复入队，队列指数增长、永不结束。

考点：判重的必要性（缺了判重 = 灾难）。

解析：0 出队，入队 1、2；1 出队，入队 0、2（0、2 已访问过）；2 出队，入队 0、1……每次出队都新增两个邻居，队列单调膨胀。这不是「多访问一次」，而是无限增长直到内存耗尽。

排除法：不会正常结束；不会输出固定序列；不会少点——是多到没完没了。