给定图G的V顶点总数和E边总数，如何计算图的强连接组件中最大的强连接组件和最少数量的顶点和边。
例如。对于具有5个顶点和7个边的图形，所连接组件的最小大小为3。可以对该图进行建模，以便有更多的连接组件，但最小值为3。
我面临的问题是没有向我提供边缘信息。仅给出边的总数。我想通过深度优先搜索使用Tarjan's算法，但是我需要边缘信息。
是否有可能找到具有最小顶点和边数，仅顶点总数和边数总数的强连接组件的大小。
最佳答案
我能想到的最简单的方法是考虑尝试利用边缘来形成尺寸为Complete Graphs的大小为1，然后为2的组件，以此类推，直到找到有效的组件为止。
大小为n的完整图具有（n2-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是解。