Leetcode 332. 重新安排行程
题目
给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 出发。
说明:
如果存在多种有效的行程，你可以按字符自然排序返回最小的行程组合。例如，行程 [“JFK”, “LGA”] 与 [“JFK”,“LGB”] 相比就更小，排序更靠前所有的机场都用三个大写字母表示（机场代码）。假定所有机票至少存在一种合理的行程。
测试样例
示例 1:
输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
输出: ["JFK", "MUC", "LHR", "SFO", "SJC"]
示例 2:
输入: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出: ["JFK","ATL","JFK","SFO","ATL","SFO"]
解释: 另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。
题解
dfs深搜回溯 建立邻接表，同时记录那种航班已经使用过了，以避免重复使用。详细过程见代码
代码
vector
<string
> ans
;
unordered_map
<string
,vector
<string
>> ticket
;
unordered_map
<string
,vector
<int>> use
;
bool dfs(string
& now
,int begin
,int n
){
if(begin
== n
){
return true;
}else{
int size
= ticket
[now
].size();
for(int i
=0; i
<size
; i
++){
if(!use
[now
][i
]){
ans
.push_back(ticket
[now
][i
]);
use
[now
][i
] = 1;
if(dfs(ticket
[now
][i
],begin
+1,n
)) return true;
ans
.pop_back();
use
[now
][i
] = 0;
}
}
}
return false;
}
vector
<string
> findItinerary(vector
<vector
<string
>>& tickets
) {
int n
= tickets
.size();
for(int i
=0; i
<n
; i
++){
int j
,n
= ticket
[tickets
[i
][0]].size();
for(j
=0; j
<n
; j
++)
if(ticket
[tickets
[i
][0]][j
] >= tickets
[i
][1]) break;
ticket
[tickets
[i
][0]].insert(ticket
[tickets
[i
][0]].begin()+j
,tickets
[i
][1]);
use
[tickets
[i
][0]].push_back(0);
}
string beginC
= "JFK";
ans
.push_back(beginC
);
dfs(beginC
,0,n
);
return ans
;
}
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reconstruct-itinerary 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
