图论·单选训练2（2）

第 1 题（单选）

并查集的路径压缩主要发生在（）操作中。

{{ select(1) }}

• lower_bound
• sort
• find
• push_back

第 2 题（单选）

用邻接表存储含 n 个点、m 条边的稀疏图，空间通常为（）。

{{ select(2) }}

• O(n^2)
• O(2^n)
• O(n+m)
• O(m^2)

第 3 题（单选）

DFS 枚举图中从 s 到 t 的所有简单路径时，若进入 v 前执行 vis[v]=true，递归返回后却没有恢复 vis[v]=false，则（）。

{{ select(3) }}

• 只会导致路径顺序改变，不影响结果
• 可能把其他分支中本应可用的节点仍视为已访问，从而漏解
• 会自动把 DFS 变成 BFS
• 只要图无环就一定没有影响

第 4 题（单选）

在带钥匙的网格 BFS 中，同一位置 (x,y) 可能携带不同钥匙集合 mask。若 visited 只按 (x,y) 记录，主要风险是（）。

{{ select(4) }}

• BFS 一定会变成深度优先
• 不同 mask 的状态被错误合并，可能漏掉能开门的路径
• 只会多使用 O(1) 空间
• 只影响输出格式

第 5 题（单选）

使用优先队列优化 Dijkstra 时，弹出 (d,u) 后常写 if(d!=dist[u]) continue;，这是为了（）。

{{ select(5) }}

• 允许处理负权边
• 保证每个点恰好入队一次
• 把有向图自动变成无向图
• 跳过优先队列中已过时的距离记录