पायथन में स्वैपिंग के बाद समकक्ष जोड़े की संख्या को अधिकतम करने का कार्यक्रम

मान लीजिए हमारे पास संख्या A की सूची है और समान लंबाई की संख्या B की सूची है। हमारे पास संख्या C की एक 2D सूची भी है जहां प्रत्येक तत्व [i, j] के रूप का है, यह इंगित करता है कि हम A[i] और A[j] को जितनी बार चाहें स्वैप कर सकते हैं। हमें उन युग्मों की अधिकतम संख्या ज्ञात करनी है जहाँ अदला-बदली के बाद A[i] =B[i]।

इसलिए, यदि इनपुट ए =[5, 6, 7, 8], बी =[6, 5, 8, 7], सी =[[0, 1], [2, 3]] जैसा है, तो आउटपुट 4 होगा, क्योंकि हम A[0] को A[1] के साथ और A[2] को A[3] के साथ स्वैप कर सकते हैं।

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

• N :=A का आकार
• ग्राफ :=दिए गए किनारों को दोतरफा जोड़कर एक ग्राफ।
• उत्तर:=0
• देखा:=आकार N की एक सूची और गलत से भरें
• आपके लिए 0 से N की सीमा में, करें
  • यदि देखा जाए[u] शून्य है, तो
    • कतार:=एक कतार और आप डालें
    • देखा[यू] :=सच
    • कतार में प्रत्येक नोड के लिए, करें
      • ग्राफ में प्रत्येक नी के लिए[नोड], करते हैं
        • अगर देखा [नेई] झूठा है, तो
          • कतार के अंत में nei डालें
          • देखा[nei] :=सच
    • गिनती :=एक नक्शा जिसमें कतार में सभी i के लिए B[i] तत्वों की गिनती होती है
    • कतार में प्रत्येक i के लिए, करते हैं
      • अगर गिनती[A[i]] शून्य नहीं है, तो
        • गिनती[ए[i]] :=गिनती[ए[i]] - 1
        • उत्तर:=उत्तर + 1
• वापसी उत्तर

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

उदाहरण

from collections import Counter
class Solution:
   def solve(self, A, B, edges):
      N = len(A)
      graph = [[]
      for _ in range(N)]
         for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
      ans = 0
      seen = [False] * N
      for u in range(N):
         if not seen[u]:
            queue = [u]
            seen[u] = True
            for node in queue:
               for nei in graph[node]:
                  if not seen[nei]:
                     queue.append(nei)
                     seen[nei] = True
            count = Counter(B[i] for i in queue)
            for i in queue:
               if count[A[i]]:
                  count[A[i]] -= 1
            ans += 1
      return ans
ob = Solution()
A = [5, 6, 7, 8]
B = [6, 5, 8, 7]
C = [[0, 1],[2, 3]]
print(ob.solve(A, B, C))

इनपुट

[5, 6, 7, 8], [6, 5, 8, 7], [[0, 1],[2, 3]]

आउटपुट

4