私は次のようになります整数のペアのベクトルを持つC++でのペア

Question

のベクターからのグループのベクトルを生成します。

pair[0] = {1, 2} 
pair[1] = {5, 7} 
pair[2] = {9, 3} 
pair[3] = {4, 6} 
pair[4] = {8, 6} 
pair[5] = {1, 3} 
pair[6] = {9, 6} 

私はペアのいずれかで一緒に来る数字をグループ化する必要があります。

たとえば、番号1は2と3とペアになっているため、グループにまとめられています。 3も9と対になり、9は6と対になり、6は4と対になるので、第1のグループの一部である必要もあります。

番号5と7は、最初のグループの他の数字と重複しないので、それらを自分のグループに入れる必要があります。

得られたベクターは、のようなものにする必要があります：

group[0] = {1, 2, 3, 4, 6, 8, 9} 
group[1] = {5, 7} 

私はこれをしたい、と私は効率的な方法でこれをしたいです。ありがとうございました。

Answer 1

この問題は、Disjoint-set Data Structureを直接適用することで解決できます。

ペアのリストを確認し、見つかった各数値のシングルトンセットを作成します。次に対をもう一度実行して、の組合の操作を各組の2つの要素で表されるセットで実行します。

この記事で説明されている正しい表現が与えられている場合、これは線形の時間と空間で非常に効率的に行うことができます。