algorithm - 使用不相交集数据结构，图论

Question

我在空闲时间练习解决编程问题。这个问题我前段时间发现了，但仍然不知道如何解决：

对于具有 n 个顶点和 m 个边（均小于 2 × 10 ⁶）的给定无向图，我需要将其顶点拆分为尽可能多的组，但有一个条件：来自不同组的每一对顶点通过边连接。每个顶点恰好在一个组中。最后，我需要知道每个组的大小。

当我想出这个解决方案时，我感到很自豪：考虑原始图的补充图并为其使用不相交集数据结构。它给了我们正确的答案（不难证明）。但这只是理论上的解决方案。在给定的约束下，它非常非常糟糕，不是最优的。但我相信这种方法可以以某种方式巧妙地解决。但是怎么做？

任何人都可以帮忙吗？

编辑：对于顶点从 1 到 7 和 16 条边的图：

1 3

1 4

1 5

2 3

3 4

4 5

4 7

4 6

5 6

6 7

2 4

2 7

2 5

3 5

3 7

1 7

我们有 3 个大小的组：1、2 和 4。

这些组分别是：{4}、{5,7}、{1,2,3,6}。有边连接来自不同组的每对顶点，我们不能创建更多组。

Answer 1

我认为您缺少的唯一要素是如何处理稀疏图。

让我们从寻找最大可能的完整图的角度来考虑这个问题，我唯一能做的就是将一组节点（比如 v_1，...，v_k）组合在一起，并将新的超级节点边仅提供给那些u连接的节点对所有v_1, ..., v_k。

如果您的图形的边少于 n^2/4，则随机抽样n节点对，注意哪些对没有被边连接。Union-find 是一种简单的编码方式。现在使用您通过此随机抽样找到的集合作为组来重建图形。在这个简化图上递归。（我不太确定如何分析这一步，但我相信每个样本重建周期都会以高概率将图形大小至少减少一个常数因子，因此整个过程需要近乎线性的时间。）

一旦你有一个相当密集的图（至少 n^2/4 边），你可以转换为邻接矩阵表示并完全按照你的建议做 --- 检查所有节点对，每当你看到两个节点时进行联合没有被边缘连接，并读取集合。