পাইথনে ফ্লাইট ইটিনেরারি (বিমান যাত্রা পথ) সঠিক অর্ডারে বের করা

সমস্যা বিবরণ

ফ্লাইটের লিস্ট দেওয়া আছে [origin, destination] পেয়ার হিসেবে। লিস্ট শাফলড (shuffled) আছে। সঠিক ক্রমে বিমানবন্দর ভিজিটের পথ বের করতে হবে। একাধিক বৈধ ইটিনেরারি হলে লেক্সিকোগ্রাফিক্যালি সবচেয়ে ছোটটি রিটার্ন করুন।

উদাহরণ

Input:  flights = [["Mumbai", "Kolkata"], ["Delhi", "Mumbai"], ["Kolkata", "Delhi"]]
Output: ['Delhi', 'Mumbai', 'Kolkata', 'Delhi']

সমাধানের কৌশল

এই সমস্যাটি ইউলার পাথ (Eulerian Path) খুঁজে বের করার সমস্যা। dirigida গ্রাফে প্রতিটি এজ একবার ভিজিট করতে হবে।

অ্যালগরিদম (Hierholzer's Algorithm)

1. এডজেসেন্সি লিস্ট বানান, আউট-ডিগ্রি ও ইন-ডিগ্রি গণনা করুন
2. প্রতিটি নোডের প্রতিবেশী লিস্ট সর্ট করুন (লেক্সিকোগ্রাফিক্যাল অর্ডারের জন্য)
3. শুরুর নোড খুঁজুন: out_degree - in_degree == 1
4. DFS দিয়ে পথ বানান (পোস্ট-অর্ডার)
5. রেজাল্ট রিভার্স করুন

পাইথন কোড

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 = None
        end = None
        for airport in adj_list.keys():
            diff = outs[airport] - ins[airport]
            if diff == 1:
                if start: return None
                start = airport
            elif diff == -1:
                if end: return None
                end = airport
            elif diff != 0:
                return None
        
        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']

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(E log E) — E = ফ্লাইট সংখ্যা (সর্টিং কারণে)
• স্থান জটিলতা: O(V + E) — গ্রাফ স্টোরেজ

মূল বিষয়বস্তু

• ইউলার পাথ: প্রতিটি এজ একবার ভিজিট
• Hierholzer's Algorithm: পোস্ট-অর্ডার DFS দিয়ে পথ বানানো
• লেক্সিকোগ্রাফিক্যাল অর্ডারের জন্য অ্যাডজেসেন্সি লিস্ট সর্ট করুন