算法题：690. 最大化交换后的等价对数

Question

题目描述

You are given a list of integers of the same length A and B. You are also given a two-dimensional list of integers C where each element is of the form [i, j] which means that you can swap A[i] and A[j] as many times as you want.

Return the maximum number of pairs where A[i] = B[i] after the swapping.

Constraints

n ≤ 100,000 where n is the length of A and B
m ≤ 100,000 where m is the length of C
Example 1
Input
A = [1, 2, 3, 4]
B = [2, 1, 4, 3]
C = [
    [0, 1],
    [2, 3]
]
Output
4
Explanation
We can swap A[0] with A[1] then A[2] with A[3].

题目地址

https://binarysearch.com/problems/Maximize-the-Number-of-Equivalent-Pairs-After-Swaps

前置知识

• 并查集
• BFS
• DFS

并查集

思路

这道题的核心在于如果 A 中的 [0,1] 可以互换，并且 [1,2] 可以互换，那么 [0,1,2] 可以任意互换。

也就是说互换具有联通性。这种联通性对做题有帮助么？有的！

根据 C 的互换关系，我们可以将 A 分为若干联通域。对于每一个联通域我们可以任意互换。因此我们可以枚举每一个联通域，对联通域中的每一个索引 i ，我们看一下 B 中是否有对应 B[j] == A[i] 其中 i 和 j 为同一个联通域的两个点。

具体算法：

• 首先根据 C 构建并查集。
• 然后根据将每一个联通域存到一个字典 group 中，其中 group[i] = list，i 为联通域的元，list 为联通域的点集合列表。
• 枚举每一个联通域，对联通域中的每一个索引 i ，我们看一下 B 中是否有对应 B[j] == A[i] 其中 i 和 j 为同一个联通域的两个点。累加答案即可

代码

代码支持：Python3

Python3 Code:

class UF:
  def __init__(self, M):
      self.parent = {}
      self.cnt = 0
      # 初始化 parent，size 和 cnt
      for i in range(M):
          self.parent[i] = i
          self.cnt += 1

  def find(self, x):
      if x != self.parent[x]:
          self.parent[x] = self.find(self.parent[x])
          return self.parent[x]
      return x
  def union(self, p, q):
      if self.connected(p, q): return
      leader_p = self.find(p)
      leader_q = self.find(q)
      self.parent[leader_p] = leader_q
      self.cnt -= 1
  def connected(self, p, q):
      return self.find(p) == self.find(q)

class Solution:
    def solve(self, A, B, C):
        n = len(A)
        uf = UF(n)
        for fr, to in C:
            print(fr, to)
            uf.union(fr, to)
        group = collections.defaultdict(list)

        for i in uf.parent:
            group[uf.find(i)].append(i)
        ans = 0
        for i in group:
            indices = group[i]
            values = collections.Counter([A[i] for i in indices])
            for i in indices:
                if values[B[i]] > 0:
                    values[B[i]] -= 1
                    ans += 1
        return ans

复杂度分析

令 n 为数组 A 的长度，v 为图的点数，e 为图的边数。

• 时间复杂度：$O(n+v+e)$
• 空间复杂度：$O(n)$

总结

我们也可以使用 BFS 或者 DFS 来生成 group，生成 group 后的逻辑大家都是一样的，这两种解法留给大家来实现吧。