c++ - 按公共(public)元素对列表进行分组

Question

我正在寻找一种聪明/快速的 C++ 算法，当它们包含公共(public)对象时，它允许我对多个对象列表进行分组。假设我有 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]

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

Answer 1

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

即

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

这些列表归纳出一个图:每个元素有一个顶点，如果相应的元素出现在同一个列表中，则两个顶点相连。

在我看来，您要计算的是 connected components图的。