循环调用Kruskal算法求解各SCC的MST的最坏时间复杂度是多少

你的猜想完全正确，该算法的最坏时间复杂度就是O(E log V)，最坏情况确实出现在K=1的场景下。

• 首先拆分算法总耗时：总时间 = Kosaraju算法求SCC的耗时 + 所有SCC运行Kruskal算法的总耗时。其中Kosaraju算法的时间复杂度为O(V+E)，量级远小于O(E log V)，因此整体时间的瓶颈在所有SCC运行Kruskal的总耗时上。
• 设第i个SCC包含v_i个顶点、e_i条内部边，显然所有SCC的顶点和满足Σv_i = V，所有SCC的内部边和满足Σe_i ≤ E（原图的跨SCC边不属于任何一个SCC的内部边，不会参与Kruskal计算）。
• 单个SCC运行Kruskal的时间复杂度为O(e_i log v_i)，因此所有SCC的总运行时间为ΣO(e_i log v_i)。
• 对求和式取上界：因为任意SCC的顶点数v_i ≤ V，因此log v_i ≤ log V，代入可得Σe_i log v_i ≤ log V * Σe_i ≤ E log V。当K=1时，整个图是单个强连通分量，此时v_1=V、e_1=E，刚好取到这个上界，因此这就是算法的最坏时间复杂度。
• 若K的取值更大，总耗时只会更低：比如极端情况K=V时每个SCC仅含1个顶点，无需运行Kruskal算法，总耗时仅为O(V+E)，远低于最坏情况。

# 求图G的强连通分量数量K
Number of SCC, K <- apply Kosaraju's algorithm on Graph G // 时间复杂度 O(V + E)

# 遍历每个强连通分量求MST
Loop through K components:
  对当前分量运行Kruskal算法

内容的提问来源于stack exchange，提问作者Math.anony