पायथन में आसन्न जोड़े से ऐरे को पुनर्स्थापित करने का प्रोग्राम

मान लीजिए हमारे पास adPair नामक एक 2D ऐरे है जिसका आकार n-1 है जहां प्रत्येक adPair[i] में दो तत्व [ui, vi] हैं जो दर्शाते हैं कि तत्व ui और vi nums नामक ऐरे में आसन्न हैं, nums में n अद्वितीय तत्व हैं। हमें ऐरे nums ढूंढना है। यदि कई समाधान हैं, तो उनमें से कोई भी वापस करें।

उदाहरण के लिए, यदि इनपुट adPair = [[3,2],[4,5],[4,3]] है, तो आउटपुट [2,3,4,5] होगा।

हल करने के चरण

1. my_map := अलग-अलग कुंजियों के लिए सूची स्टोर करने के लिए एक खाली मैप
2. adPair में प्रत्येक जोड़ी (a, b) के लिए:
   • b को my_map[a] के अंत में जोड़ें
   • a को my_map[b] के अंत में जोड़ें
3. my_map में प्रत्येक कुंजी a और मान सूची l के लिए:
   • यदि l का आकार 1 है, तो:
     • nums := [a, l[0]] दो तत्वों वाली सूची
     • लूप से बाहर निकलें
4. i को 1 से len(adPair) - 1 तक लूप चलाएं:
   • a, b := my_map[nums[-1]]
   • यदि a == nums[-2], तो b को nums के अंत में जोड़ें
   • अन्यथा, a को nums के अंत में जोड़ें
5. 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]