图论·单选训练1

第 1 题（单选）

若使用 Floyd 求全源最短路，时间复杂度是（）。

{{ select(1) }}

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

第 2 题（单选）

Dijkstra 使用二叉堆优化，常见复杂度是（）。

{{ select(2) }}

• O(n^3)
• O((n+m)log n)
• O(2^n)
• O(nm)

第 3 题（单选）

Kruskal 的主要复杂度来自（）。

{{ select(3) }}

• 矩阵乘法
• DFS 深度
• 排序边
• 读入点权

第 4 题（单选）

Tarjan 求强连通分量的复杂度是（）。

{{ select(4) }}

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

第 5 题（单选）

树链剖分将树上路径拆成若干重链段，单次路径操作通常拆成（）段级别。

{{ select(5) }}

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