c++ - 按常见元素对列表进行分组

Question

我正在寻找一种聪明/快速的 C++ 算法，当它们包含常见的对象时，它可以让我对多个对象列表进行分组。假设我有 N 个列表，每个列表包含与一个元素 E 关联的 1..M 个对象 (O)：

[O1, O2]     -> E1
[O3]         -> E2
[O1, O4, O5] -> E3
[O2, O5]     -> E4
[O3, O6]     -> E5

我希望将它们重新排列为以下内容：

[O1, O2, O4, O5] -> [E1, E3, E4]
[O3, O6]         -> [E2, E5]

结果将所有公共对象与所有关联元素组合在一起。最终没有对象在列表之间共享。

Answer 1

对于每个对象，计算哪些元素包含它。

IE

01 -> [E1, E3]
02 -> [E4]
03 -> [E2, E5]
04 -> [E3]
05 -> [E3, E4]
06 -> [E5]

这些列表产生了一个图：每个元素都有一个顶点，如果相应的元素出现在同一个列表中，则两个顶点是连接的。

在我看来，您要计算的是图形的连通分量。