Я приведу здесь более общее решение проблемы:
Вы можете остановиться несколько раз в одном и том же аэропорту, но вы должны использовать каждый билет ровно 1 раз
Вы можете иметь более 1 билета на каждую часть поездки.
Каждый билет содержит SRC и DST аэропорта.
Все ваши билеты отсортированы случайным образом.
Вы забыли исходный аэропорт отправления (самый первый рейс) и пункт назначения (последний день).
Мой метод возвращает список городов (вектор), которые содержат все указанные города, если такая цепочка существует, и пустой список в противном случае. Когда есть несколько способов путешествовать по городам, метод возвращает наименьший лексикографический список.
#include<vector>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<set>
#include<map>
using namespace std;
struct StringPairHash
{
size_t operator()(const pair<string, string> &p) const {
return hash<string>()(p.first) ^ hash<string>()(p.second);
}
};
void calcItineraryRec(const multimap<string, string> &cities, string start,
vector<string> &itinerary, vector<string> &res,
unordered_set<pair<string, string>, StringPairHash> &visited, bool &found)
{
if (visited.size() == cities.size()) {
found = true;
res = itinerary;
return;
}
if (!found) {
auto pos = cities.equal_range(start);
for (auto p = pos.first; p != pos.second; ++p) {
if (visited.find({ *p }) == visited.end()) {
visited.insert({ *p });
itinerary.push_back(p->second);
calcItineraryRec(cities, p->second, itinerary, res, visited, found);
itinerary.pop_back();
visited.erase({ *p });
}
}
}
}
vector<string> calcItinerary(vector<pair<string, string>> &citiesPairs)
{
if (citiesPairs.size() < 1)
return {};
multimap<string, string> cities;
set<string> uniqueCities;
for (auto entry : citiesPairs) {
cities.insert({ entry });
uniqueCities.insert(entry.first);
uniqueCities.insert(entry.second);
}
for (const auto &startCity : uniqueCities) {
vector<string> itinerary;
itinerary.push_back(startCity);
unordered_set<pair<string, string>, StringPairHash> visited;
bool found = false;
vector<string> res;
calcItineraryRec(cities, startCity, itinerary, res, visited, found);
if (res.size() - 1 == cities.size())
return res;
}
return {};
}
Вот пример использования:
int main()
{
vector<pair<string, string>> cities = { {"Y", "Z"}, {"W", "X"}, {"X", "Y"}, {"Y", "W"}, {"W", "Y"}};
vector<string> itinerary = calcItinerary(cities); // { "W", "X", "Y", "W", "Y", "Z" }
// another route is possible {W Y W X Y Z}, but the route above is lexicographically smaller.
cities = { {"Y", "Z"}, {"W", "X"}, {"X", "Y"}, {"W", "Y"} };
itinerary = calcItinerary(cities); // empty, no way to travel all cities using each ticket exactly one time
}