在C ++中重建行程
因此，如果输入类似于[[“MUC”，“LHR”]，[“JFK”，“MUC”]，[“SFO”，“SJC”]，[“LHR”，“SFO”]]，则输出将是[“JFK”，“MUC”，“LHR”，“SFO”，“SJC”]。
为了解决这个问题，我们将遵循以下步骤-
定义数组ret和一个称为图的映射。
定义一个称为visit的方法。这将以机场名称为输入
而图[机场]的大小不为0
x：=图[机场]的第一个元素
从图表[机场]删除第一个元素
致电拜访(x)
将机场插入ret
现在从主要方法中，执行以下操作-
为我在0到代码行列数组的范围内
u：=tickets[i，0]，v：=tickets[i，1]，将v插入图表[u]
visit（“JFK”），因为这是第一个机场
反转列表ret并返回
例子（C++）
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector <string> ret;
map < string, multiset <string> > graph;
vector<string> findItinerary(vector<vector<string>>& tickets) {
for(int i = 0; i < tickets.size(); i++){
string u = tickets[i][0];
string v = tickets[i][1];
graph[u].insert(v);
}
visit("JFK");
reverse(ret.begin(), ret.end());
return ret;
}
void visit(string airport){
while(graph[airport].size()){
string x = *(graph[airport].begin());
graph[airport].erase(graph[airport].begin());
visit(x);
}
ret.push_back(airport);
}
};
main(){
Solution ob;
vector<vector<string>> v = {{"MUC","LHR"},{"JFK","MUC"},{"SFO","SJC"},{"LHR","SFO"}};
print_vector(ob.findItinerary(v));
}输入值
[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出结果
[JFK, MUC, LHR, SFO, SJC, ]