c++ - 在 C++ 中合并 union 集

Question

从 unsigned int 的 vector vector 开始...

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

我想合并 union 集(即具有共同元素的 vector )。

例如，作为输入:

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。

Answer 1

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

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

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