深度优先搜索
图
欧拉回路
题目描述
给你一份航线列表 tickets
,其中 tickets[i] = [fromi , toi ]
表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK
(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK
开始。如果存在多种有效的行程,请你按字典排序返回最小的行程组合。
例如,行程 ["JFK", "LGA"]
与 ["JFK", "LGB"]
相比就更小,排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
示例 1:
输入: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出: ["JFK","MUC","LHR","SFO","SJC"]
示例 2:
输入: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出: ["JFK","ATL","JFK","SFO","ATL","SFO"]
解释: 另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ,但是它字典排序更大更靠后。
提示:
1 <= tickets.length <= 300
tickets[i].length == 2
fromi .length == 3
toi .length == 3
fromi
和 toi
由大写英文字母组成
fromi != toi
解法
方法一
Python3 Java C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution :
def findItinerary ( self , tickets : List [ List [ str ]]) -> List [ str ]:
graph = defaultdict ( list )
for src , dst in sorted ( tickets , reverse = True ):
graph [ src ] . append ( dst )
itinerary = []
def dfs ( airport ):
while graph [ airport ]:
dfs ( graph [ airport ] . pop ())
itinerary . append ( airport )
dfs ( "JFK" )
return itinerary [:: - 1 ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 class Solution {
void dfs ( Map < String , Queue < String >> adjLists , List < String > ans , String curr ) {
Queue < String > neighbors = adjLists . get ( curr );
if ( neighbors == null ) {
ans . add ( curr );
return ;
}
while ( ! neighbors . isEmpty ()) {
String neighbor = neighbors . poll ();
dfs ( adjLists , ans , neighbor );
}
ans . add ( curr );
return ;
}
public List < String > findItinerary ( List < List < String >> tickets ) {
Map < String , Queue < String >> adjLists = new HashMap <> ();
for ( List < String > ticket : tickets ) {
String from = ticket . get ( 0 );
String to = ticket . get ( 1 );
if ( ! adjLists . containsKey ( from )) {
adjLists . put ( from , new PriorityQueue <> ());
}
adjLists . get ( from ). add ( to );
}
List < String > ans = new ArrayList <> ();
dfs ( adjLists , ans , "JFK" );
Collections . reverse ( ans );
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 class Solution {
public :
vector < string > findItinerary ( vector < vector < string >>& tickets ) {
unordered_map < string , priority_queue < string , vector < string > , greater < string >>> g ;
vector < string > ret ;
// Initialize the graph
for ( const auto & t : tickets ) {
g [ t [ 0 ]]. push ( t [ 1 ]);
}
findItineraryInner ( g , ret , "JFK" );
ret = { ret . rbegin (), ret . rend ()};
return ret ;
}
void findItineraryInner ( unordered_map < string , priority_queue < string , vector < string > , greater < string >>>& g , vector < string >& ret , string cur ) {
if ( g . count ( cur ) == 0 ) {
// This is the end point
ret . push_back ( cur );
return ;
} else {
while ( ! g [ cur ]. empty ()) {
auto front = g [ cur ]. top ();
g [ cur ]. pop ();
findItineraryInner ( g , ret , front );
}
ret . push_back ( cur );
}
}
};