c++ - 共通要素によるリストのグループ化

Question

内部に共通のオブジェクトが含まれている場合に、オブジェクトの複数のリストをグループ化できる、巧妙で高速な C++ アルゴリズムを探しています。N 個のリストがあり、それぞれに 1 つの要素 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

オブジェクトごとに、それを含む要素を計算します。

すなわち

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

これらのリストはグラフを誘導します。要素ごとに頂点があり、対応する要素が同じリストに表示される場合、2 つの頂点が接続されます。

あなたが計算したいのは、グラフの連結成分であるように私には思えます。