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

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

इसलिए, यदि इनपुट adPair =[[3,2], [4,5], [4,3]] जैसा है, तो आउटपुट [2,3,4,5]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• my_map :=अलग-अलग कुंजियों की सूची स्टोर करने के लिए एक खाली नक्शा
• विज्ञापन जोड़ी में प्रत्येक जोड़ी (ए, बी) के लिए, करें
  • my_map[a] के अंत में b डालें[a]
  • my_map[b] के अंत में a डालें[b]
• my_map में प्रत्येक कुंजी a और मान सूची l के लिए, करें
  • यदि l का आकार 1 के समान है, तो
    • अंक:=दो तत्वों वाली एक सूची (a, l[0])
    • लूप से बाहर आएं
• i के लिए 1 से लेकर adPair -1 के आकार तक के लिए
  • a, b :=my_map[अंकों का अंतिम तत्व]
  • यदि a, अंकों के दूसरे अंतिम तत्व के समान है, तो
    • अंकों के अंत में b डालें
  • अन्यथा,
    • अंकों के अंत में a डालें
• रिटर्न अंक

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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]