โปรแกรมหาลำดับสนามบินที่ถูกต้องจากรายการเที่ยวบินใน Python

มีรายการเที่ยวบินเป็นคู่ [origin, destination] สับสน ต้องหาลำดับสนามบินที่เยี่ยมชมถูกต้อง หากมีหลายคำตอบ ให้คำตอบที่เล็กที่สุดในลำดับเลขศัพท์ (Lexicographically smallest)

ตัวอย่าง: flights = [["Mumbai", "Kolkata"], ["Delhi", "Mumbai"], ["Kolkata", "Delhi"]] → ['Delhi', 'Mumbai', 'Kolkata', 'Delhi']

แนวทาง (Hierholzer's Algorithm สำหรับ Eulerian Path)

1. สร้าง adjacency list นับ in-degree/out-degree
2. หาจุดเริ่มต้น: out - in = 1 (เริ่ม) หรือ in - out = 1 (จบ) หรือ min key ถ้าเป็น cycle
3. DFS แบบ iterative ใช้ stack เก็บเส้นทาง
4. คืนค่า path ย้อนกลับ

ตัวอย่างโค้ด

from collections import defaultdict

class Solution:
    def solve(self, flights):
        ins = defaultdict(int)
        outs = defaultdict(int)
        adj_list = defaultdict(list)
        
        for s, e in flights:
            adj_list[s].append(e)
            outs[s] += 1
            ins[e] += 1
        
        for l in adj_list.values():
            l.sort()
        
        start = end = None
        for airport in adj_list.keys():
            diff = outs[airport] - ins[airport]
            if diff == 1:
                if start: return
                start = airport
            elif diff == -1:
                if end: return
                end = airport
            elif diff != 0:
                return
        
        start = start if start else min(adj_list.keys())
        ans = []
        
        def dfs(airport):
            while outs[airport]:
                nxt = len(adj_list[airport]) - outs[airport]
                outs[airport] -= 1
                dfs(adj_list[airport][nxt])
            ans.append(airport)
        
        dfs(start)
        return ans[::-1]

ob = Solution()
flights = [["Mumbai", "Kolkata"], ["Delhi", "Mumbai"], ["Kolkata", "Delhi"]]
print(ob.solve(flights))  # ['Delhi', 'Mumbai', 'Kolkata', 'Delhi']

อินพุต

[["Mumbai", "Kolkata"], ["Delhi", "Mumbai"], ["Kolkata", "Delhi"]]

เอาต์พุต

['Delhi', 'Mumbai', 'Kolkata', 'Delhi']