图论·单选训练5

第 1 题（单选）

DAG 中有边 1→3、2→3、3→4。Kahn 拓扑排序开始时可进入队列的顶点数为（）。

{{ select(1) }}

• 1
• 2
• 3
• 4

第 2 题（单选）

无权树中，设 w=LCA(u,v)，depth 表示深度，则 u、v 间距离为（）。

{{ select(2) }}

• depth[w]
• depth[u]+depth[v]
• depth[u]-depth[v]
• depth[u]+depth[v]-2*depth[w]

第 3 题（单选）

可撤销并查集通常不使用普通路径压缩，主要原因是（）。

{{ select(3) }}

• 路径压缩会使 find 变成 O(n)
• 路径压缩只适用于有向图
• 路径压缩会改变集合数量
• 一次 find 可能改写多个父指针，使历史状态难以按栈精确撤销

第 4 题（单选）

并查集带权值时，额外维护的是（）。

{{ select(4) }}

• 线段树懒标记
• 拓扑序
• 字符串哈希
• 节点到父亲或根的关系量

第 5 题（单选）

可撤销并查集通常不能使用普通路径压缩，主要因为（）。

{{ select(5) }}

• 不能合并
• 必须递归
• 路径压缩修改太多信息不易回滚
• find 会变慢到 O(0)