สมมติว่าเรามีรายการตั๋วที่แทนด้วยคู่ของสนามบินออกเดินทางและถึง เช่น [from, to] เราต้องหา itinerary ตามลำดับ ตั๋วทั้งหมดเป็นของชายคนหนึ่งที่ออกเดินทางจาก Chennai ดังนั้น itinerary ต้องเริ่มต้นด้วย Chennai
ดังนั้น ถ้า input เป็นแบบ [["Mumbai", " Kolkata"], ["Chennai ", " Mumbai"], ["Delhi", "Bangalore"], ["Kolkata", " Delhi"]] แล้ว output จะเป็น ["Chennai", " Mumbai", " Kolkata", " Delhi", "Bangalore"]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ −
กำหนด array ret และ map ชื่อ graph
กำหนด method ชื่อ visit ซึ่งจะรับชื่อสนามบินเป็น input
while size ของ graph[airport] ไม่ใช่ 0
x := first element ของ graph[airport]
ลบ first element ออกจาก graph[airport]
เรียก visit(x)
insert airport ลงใน ret
ตอนนี้จาก main method ให้ทำดังนี้ −
for i ใน range 0 ถึง size ของ tickers array
u := tickets[i, 0], v := tickets[i, 1], insert v ลงใน graph[u]
visit(“Chennai”) เนื่องจากนี่คือสนามบินแรก
reverse list 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("Chennai"); 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 = {{"Mumbai", "Kolkata"}, {"Chennai", "Mumbai"}, {"Delhi", "Bangalore"}, {"Kolkata", "Delhi"}}; print_vector(ob.findItinerary(v)); }อินพุต
{{"Mumbai", "Kolkata"}, {"Chennai", "Mumbai"}, {"Delhi", "Bangalore"}, {"Kolkata", "Delhi"}}เอาต์พุต
[Chennai, Mumbai, Kolkata, Delhi, Bangalore, ]
