java - 强连通分量

Question

给定图 G 的 V 顶点总数和 E 边总数，如何计算图强连通分量中顶点和边数最少的最大强连通分量。

例如。对于具有 5 个顶点和 7 个边的图，连通分量的最小大小为 3。
可以对该图进行建模，以便有更多的连通分量，但最小值为 3。

我面临的问题是边缘信息没有提供给我。仅给出边的总数。我想使用Tarjan's使用深度优先搜索的算法，但我需要边缘信息。

是否可以找到具有最小顶点和边的强连通分量的大小，即顶点总数和边总数。

Answer 1

我能想到的最简单的方法是考虑尝试利用边缘来形成 Complete Graphs 的组件。尺寸为 1，然后为 2，依此类推，直到找到合适的尺寸。

大小为 n 的完整图有 (n² - n)/2 条边。因此，拆分为大小为 n 的组件将类似于

numFullComponents := V/n //integer division
numEdgesUsed := numFullComponents * n * (n-1) / 2 //This is edges from full components
    + (V%n) * (V%n - 1)/2 //a complete graph on the remainder nodes

然后，您可以将所使用的边数与图中的边数进行比较。至少使用 E 条边的最小 n 就是解决方案。