পাইথনে এডজেসেন্ট জোড়া থেকে অ্যারে রিস্টোর করার প্রোগ্রাম

আমাদের একটি ২ডি অ্যারে আছে adPair আকার n-1 যেখানে প্রতিটি adPair[i] দুটি উপাদান [ui, vi] ধারণ করে যা নির্দেশ করে যে ui এবং vi nums অ্যারেতে এডজেসেন্ট, nums-এ n টি ইউনিক উপাদান আছে। আমাদের nums অ্যারেটি বের করতে হবে। যদি একাধিক সমাধান থাকে, তবে যেকোনো একটি রিটার্ন করুন।

উদাহরণস্বরূপ, ইনপুট adPair = [[3,2],[4,5],[4,3]] হলে আউটপুট হবে [2,3,4,5]।

সমাধানের ধাপসমূহ

• my_map := একটি খালি ম্যাপ যা বিভিন্ন কী-এর জন্য লিস্ট সংরক্ষণ করবে

• adPair-এর প্রতিটি জোড়া (a, b) এর জন্য:

  • b-কে my_map[a]-এর শেষে যোগ করুন

  • a-কে my_map[b]-এর শেষে যোগ করুন

• my_map-এর প্রতিটি কী a এবং ভ্যালু লিস্ট l এর জন্য:

  • যদি l-এর আকার ১ হয়, তবে:

    • nums := [a, l[0]] আকারের একটি লিস্ট

    • লুপ থেকে বেরিয়ে আসুন

• i = 1 থেকে adPair-এর আকার - 1 পর্যন্ত লুপ চালান:

  • a, b := my_map[nums[-1]]

  • যদি a == nums[-2] হয়, তবে:

    • b-কে nums-এর শেষে যোগ করুন

  • অন্যথায়:

    • a-কে nums-এর শেষে যোগ করুন

• nums রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালোভাবে বুঝার জন্য:

from collections import defaultdict
def solve(adPair):
    my_map = defaultdict(list)
    for a, b in adPair:
        my_map[a].append(b)
        my_map[b].append(a)
    for a, l in my_map.items():
        if len(l) == 1:
            nums = [a, l[0]]
            break
    for i in range(1, len(adPair)):
        a, b = my_map[nums[-1]]
        if a == nums[-2]:
            nums.append(b)
        else:
            nums.append(a)
    return nums

adPair = [[3,2],[4,5],[4,3]]
print(solve(adPair))

ইনপুট

[[3,2],[4,5],[4,3]]

আউটপুট

[2, 3, 4, 5]