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

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

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

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

• N := A का आकार
• graph := दिए गए किनारों को द्विदिशात्मक रूप से जोड़कर एक ग्राफ
• ans := 0
• seen := आकार N की एक सूची और False से भरें
• u के लिए 0 से N तक की रेंज में, करें
  • यदि seen[u] शून्य है, तो
    • queue := एक कतार और u डालें
    • seen[u] := True
    • प्रत्येक node के लिए queue में, करें
      • प्रत्येक nei के लिए graph[node] में, करें
        • यदि seen[nei] गलत है, तो
          • nei को queue के अंत में डालें
          • seen[nei] := True
    • count := एक मैप जिसमें queue में सभी i के लिए B[i] तत्वों की गिनती हो
    • प्रत्येक i के लिए queue में, करें
      • यदि count[A[i]] शून्येतर है, तो
        • count[A[i]] := count[A[i]] - 1
        • ans := ans + 1
• ans वापस करें

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

उदाहरण

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