# leetcode Reconstruct Itinerary

### leetcode Reconstruct Itinerary

Given a list of airline tickets represented by pairs of departure and arrival airports `[from, to]`, reconstruct the itinerary in order. All of the tickets belong to a man who departs from `JFK`. Thus, the itinerary must begin with `JFK`.

Note:

1. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary `["JFK", "LGA"]` has a smaller lexical order than `["JFK", "LGB"]`.
2. All airports are represented by three capital letters (IATA code).
3. You may assume all tickets may form at least one valid itinerary.

Example 1:
`tickets` = `[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]`
Return `["JFK", "MUC", "LHR", "SFO", "SJC"]`.

Example 2:
`tickets` = `[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]`
Return `["JFK","ATL","JFK","SFO","ATL","SFO"]`.
Another possible reconstruction is `["JFK","SFO","ATL","JFK","ATL","SFO"]`. But it is larger in lexical order.

• 从JFK出发。
• 如果有多个解，输出字典序最小的。

• 返回的答案必为n+1，n为tickets的个数
• 一张飞机票只能用一次，所以要计数。（可能重复）
• 字典序最小只需要保证我们遍历的时候从小到大遍历即可。so，建图的时候邻接表边从小到大。
• 所以C++用map, Python 排序后OrderedDict.

C++

Python

### 11 thoughts on “leetcode Reconstruct Itinerary”

1. Dan Fang says:

这个做法在处理有环图的时候 会重复访问已经访问过的边 但是leetcode test case太少 没这种情况

2. quitz says:

思路一样，但为什么会报错：

class Solution {
public:

vector findItinerary(vector<pair> tickets) {
map<string, multiset> mp;
for(auto it:tickets){
string key = it.first, val = it.second;
mp[key].insert(val);
}
vector res;
res.push_back(“JFK”);
dfs(“JFK”, res, tickets.size()+ 1, mp);
return res;
}

bool dfs(string start, vector &res, int n, map<string, multiset> &mp){
if(res.size() == n)
return true;
for(auto it = mp[start].begin();it!=mp[start].end();it++){

string dest = *it;
//cout<<"line 21 "<<start<<" "<<dest<<endl;
res.push_back(dest);
mp[start].erase(it);

if(dfs(dest,res,n,mp))
return true;

mp[start].insert(dest);
res.pop_back();
}

return false;
}
};

错误信息：terminate called after throwing an instance of 'std::logic_error'
what(): basic_string::_M_construct null not valid

3. skyaoise says:

为什么字典序最小只需要保证我们遍历的时候从小到大遍历即可？

4. chengyang says:

诶，不用初始化么？

• 我这么写的话不需要

• C++ map 会调用int()初始化为0
• python用了defaultdict和setdefault保证初始值了。
• Allianzcortex says:

对 C++11 标准的实现好像不同编译器有不同的结果？

5. Dimitar says:

Why can’t we use bool to mark the status? I tried but got TLE.

• Dimitar says:

Got the reason, the input may contain the duplicate tixs.

• Yes, so we should use int to count the number of tickets~