程序在Python中交换后最大化等效对的数量

假设我们有一个数字A的列表和一个长度相同的数字B的列表。我们还有一个数字C的二维列表，其中每个元素的格式为[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：=通过双向附加给定边的图形。

• 回答：= 0

• 看到：=大小为N的列表并用False填充

• 对于介于0到N范围内的u

• 队列：=队列并插入u

• 看过[u]：=真

• 对于队列中的每个节点，请执行

• count：=包含队列中所有i的B [i]元素计数的映射

• 为队列中的每个我做

• 如果看到[nei]为假，则

• 在队列末尾插入nei

• 看过[nei]：=真

• 对于graph [node]中的每个nei，执行

• count [A [i]]：= count [A [i]]-1

• 回答：=回答+1

• 如果count [A [i]]不为零，则

• 如果看到[u]为零，则

• 返回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