在C++中合并共同集合

Question

从一个无符号整数的向量向量开始...

vector<vector<unsigned short int> > matrix;
vector<unsigned short int> row;

我想合并共同元素的向量集合。

例如，输入如下：

matrix[0] = {0, 1, 2}
matrix[1] = {1, 10}
matrix[3] = {9}
matrix[4] = {2, 8}
matrix[5] = {7}

作为输出：

matrix[0] = {0, 1, 2, 10, 8}  // it doesn't matter the order
matrix[1] = {9}
matrix[2] = {7}

这个问题最有效的解决方案是什么？ 祝好，Vi。

- vdenotaris

Answer 1

你可以将这个问题简化为找到一个无向图的所有连通分量。其中，顶点是矩阵的行，边是非零重叠部分。Boost.Graph 库可以在O(V+E)的时间复杂度内计算出这些连通分量，其中V是顶点数（即矩阵的行数），E是边的数量（即重叠行数）。如果你不喜欢依赖 Boost，也可以使用任何可用的算法来计算强连通分量。

剩下的任务是计算该图的边缘列表表示，这取决于您是否能够对矩阵行进行排序。如果无法对矩阵行进行排序，则可以使用std::find_first_of检测非零重叠（对于具有N和M元素的2个向量，其复杂度为O(N * M)）。如果可以对它们进行排序（在O(N lg N)复杂度内），则可以使用std::set_intersection测试重叠（仅需O(N + M)复杂度）。

Boost.Graph或您的算法的输出是一组连接的组件，然后您循环遍历每个组件，并将矩阵的各个重叠行附加或合并在一起（使用std::copy，或者如果您需要它们排序，可以使用std::merge）。

- TemplateRex

---

非常抱歉打扰您，能否给我展示一个带有代码的例子？（使用boost库） - vdenotaris

@vdenotaris，我认为这个问题太大了，在此处给出完整的代码示例来解决。 - TemplateRex

Answer 2

我建议您使用不相交集合森林。对于每个集合，迭代地将数字添加到其所属集合的第一个数字。完成后，只需打印每个集合中的所有数字即可。实际上，这种实现并不难，但性能会比已提出的解决方案渐近快得多。

- Ivaylo Strandjev