4

从unsigned int...的向量的向量开始

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}

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

4

2 回答 2

2

您可以将此问题简化为查找无向图的所有连通分量。顶点是您的矩阵行，边缘是非零重叠。Boost.Graph库可以计算复杂O(V+E)度，其中V是顶点数（矩阵行）和E边数（重叠行数）。如果你不喜欢对 Boost 的依赖，你可以使用任何可用的算法来计算强连接组件。

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

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

于 2013-07-22T11:54:50.240 回答
1

我建议你使用不相交的森林。对于每个集合，迭代地将数字添加到集合的第一个数字所属的集合中。之后，只需打印每组中的所有数字。事实上，实现并不难，但性能会比已经提出的解决方案快一点。

于 2013-07-22T17:37:23.813 回答