C ++ алгоритм сортировки

Question

C ++ алгоритм сортировки

Спасибо за просмотр этого вопроса заранее.

Я пытаюсь заказать следующий список товаров:

Bpgvjdfj,Bvfbyfzc
Zjmvxouu,Fsmotsaa
Xocbwmnd,Fcdlnmhb
Fsmotsaa,Zexyegma
Bvfbyfzc,Qkignteu
Uysmwjdb,Wzujllbk
Fwhbryyz,Byoifnrp
Klqljfrk,Bpgvjdfj
Qkignteu,Wgqtalnh
Wgqtalnh,Coyuhnbx
Sgtgyldw,Fwhbryyz
Coyuhnbx,Zjmvxouu
Zvjxfwkx,Sgtgyldw
Czeagvnj,Uysmwjdb
Oljgjisa,Dffkuztu
Zexyegma,Zvjxfwkx
Fcdlnmhb,Klqljfrk
Wzujllbk,Oljgjisa
Byoifnrp,Czeagvnj

В следующем порядке:

Bpgvjdfj
Bvfbyfzc
Qkignteu
Wgqtalnh
Coyuhnbx
Zjmvxouu
Fsmotsaa
Zexyegma
Zvjxfwkx
Sgtgyldw
Fwhbryyz
Byoifnrp
Czeagvnj
Uysmwjdb
Wzujllbk
Oljgjisa
Dffkuztu

Это сделано:

Взяв первую пару и поместив имена в список
Используя второе имя пары, найдите пару, где она используется в качестве имени
Добавьте второе имя этой пары в список
Повторите 2 & 3

Я заполняю unordered_map парами, затем сортирую и добавляю каждое имя в список. Это можно увидеть в следующем коде:

westIter = westMap.begin();
std::string westCurrent = westIter->second;
westList.push_front(westCurrent);

for(int i = 0; i < 30; i++)
{
if(westMap.find(westCurrent) != westMap.end())
{
//find pair in map where first iterator is equal to "westCurrent"//append second iterator of pair to list
}
westIter++;
}

Примечание: я не уверен, что «push_front» является правильным в данный момент времени, так как я только что вставил первое значение.

Мой вопрос: может ли кто-нибудь дать мне некоторое представление о том, как я могу это сделать? Поскольку я не уверен в том, как лучше и правильно ли я думаю. Любое понимание будет оценено.

2

algorithm c++knuth sorting unordered-map

Решение

Другие решения

Создайте структуру данных, которая хранит цепочку, ее переднюю и заднюю части. Хранить в хеш-таблице с ключом «назад».
Создайте связку одиночных цепочек (по одной для каждого элемента)
Итеративно, выберите цепочку, найдите ее «фронт» в хеш-таблице (то есть найдите другую цепочку с тем же элементом, что и «назад») и объедините их
Делайте это, пока у вас не останется только одна цепь

1

Источник

Accepted Answer

Есть только одна слабость в вашем плане. Сначала вам нужно найти первого человека в сети, мистера Нью-Йорка.

Ваш алгоритм предполагает, что линия начинается с первого парня. Чтобы это работало, вы должны сначала отсканировать всю карту, чтобы найти одно имя, которое не появляется как второй элемент. Это мистер Нью-Йорк, и вы можете перейти оттуда. push_back это то, что вам нужно использовать здесь.

2