Сформировать вектор групп из вектора пар в 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, поэтому они также должны быть частью первой группы.

номера 5 и 7 не перекрываются ни с одним из других номеров из первой группы, поэтому их необходимо поместить в свою группу.

Результирующий вектор должен был бы быть что-то вроде:

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

Я хочу это, и я хочу это в эффективный способ. Спасибо.

Answer 1

Эта проблема может быть решена путем непосредственного применения Disjoint-set Data Structure.

Пройдите список пар и создайте одноэлементный набор для каждого числового значения, которое вы найдете. Затем переходите через пары еще раз, выполняя команду на множествах, представленных двумя элементами каждой пары.

Учитывая правильное представление, описанное в статье, это может быть выполнено очень эффективно в линейном времени и пространстве.