Chương trình để tối đa hóa số lượng các cặp tương đương sau khi hoán đổi bằng Python

Giả sử chúng ta có một danh sách các số A và một danh sách các số B có cùng độ dài. Chúng ta cũng có một danh sách 2D các số C trong đó mỗi phần tử có dạng [i, j], điều này cho thấy chúng ta có thể hoán đổi A [i] và A [j] nhiều lần tùy ý. Chúng ta phải tìm số cặp tối đa mà A [i] =B [i] sau khi hoán đổi.

Vì vậy, nếu đầu vào là A =[5, 6, 7, 8], B =[6, 5, 8, 7], C =[[0, 1], [2, 3]], thì đầu ra sẽ là 4, vì chúng ta có thể hoán đổi A [0] với A [1] rồi A [2] với A [3].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• N:=kích thước của A
• graph:=một biểu đồ bằng cách gắn các cạnh đã cho theo hai chiều.
• ans:=0
• saw:=danh sách kích thước N và điền sai
• đối với u trong phạm vi từ 0 đến N, thực hiện
  • nếu see [u] là 0, thì
    • queue:=một hàng đợi và chèn u
    • saw [u]:=True
    • đối với mỗi nút trong hàng đợi, hãy thực hiện
      • đối với mỗi nei trong biểu đồ [nút], thực hiện
        • nếu see [nei] là false, thì
          • chèn nei vào cuối hàng đợi
          • saw [nei]:=True
    • count:=một bản đồ chứa số lượng B [i] phần tử cho tất cả tôi trong hàng đợi
    • đối với mỗi tôi trong hàng đợi, hãy thực hiện
      • nếu số [A [i]] khác 0, thì
        • count [A [i]]:=count [A [i]] - 1
        • ans:=ans + 1
• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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

Đầu ra

4