在C++中合并合并集

Question

从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}

解决此问题的最有效解决方案是什么？致以最好的问候，维。

Answer 1

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

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

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

Answer 2

我建议您使用disjoint set forest。对于每个集合，迭代地将这些数字添加到该集合的第一个数字所属的集合。这样做之后，只需打印每个集合中的所有数字。事实上，实现并不是那么困难，但性能将比已经提出的解决方案快得多。