图论·单选训练2

第 1 题（单选）

倍增求 LCA 的预处理复杂度通常是（）。

{{ select(1) }}

• O(n^2)
• O(n log n)
• O(2^n)
• O(n)

第 2 题（单选）

一个有向图的强连通分量缩点后得到的图一定是（）。

{{ select(2) }}

• 二分图
• 完全图
• 树
• DAG

第 3 题（单选）

Tarjan 求强连通分量时，low[u] 更准确地表示（）。

{{ select(3) }}

• 以 u 为根的 DFS 子树的节点数
• 从 u 的 DFS 子树沿树边，并至多再沿一条指向当前栈内节点的边，能够到达的最小 dfn
• u 所在强连通分量的节点数
• u 到 DFS 树根的距离

第 4 题（单选）

无向图的割点是指删除该点后（）。

{{ select(4) }}

• 度数变成 0
• 所有路径变短
• 图边权变小
• 连通块数增加

第 5 题（单选）

桥是指无向图中删除后会使（）。

{{ select(5) }}

• 最短路必变短的边
• 入度为 0 的边
• 连通块数增加的边
• 权值最大的边