进阶篇作业：《并查集》

[azl397985856]

本节的作业是第 223 场周赛的 T3 1722. 执行交换操作后的最小汉明距离，官方难度为中等。 如果你熟悉并查集，能想到这道题用并查集的话就简单了。

[azl397985856]

如果 a 和 b 能交换， b 和 c 能交换， 那么显然 a 和 c 也能交换，不难发现这种交换具有传递性，因此我们可以使用并查集来解决。

具体地， 我们根据交换关系建立并查集， 将能够交换的放到一个子集中。接下来我们只要枚举所有的联通集，然后计算 source 和 target 的交集即可。

比如 source 为 [1,2,3,4], target 为 [5,6,7,8] 联通集合 A 为 {1, 2, 3} 表示索引为 1，2, 3 的三个索引可以任意相互交换，那么其对应的值集合 T1 {source[1], source[2], source[3] } ， 和 T2 {target[1], target[2], target[3] } 求交集。 计算出所有交集的集合交集个数 x， 答案就是 n - x。

枚举所有的联通子集， 可以通过如下代码实现：

        dic=collections.defaultdict(list)
        for i in range(len(source)):
            dic[uf.find(i)].append(i)

其中 dic[x] 表示以 x 为秩的联通集合。

代码:

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 minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:
        t = 0
        n = len(source)
        uf = UF(n)
        dic=collections.defaultdict(list)
        for a, b in allowedSwaps:
            uf.union(a, b)
        # 求出以 x 为秩的联通集合
        for i in range(len(source)):
            dic[uf.find(i)].append(i)
        for iss in dic.values():
            # 计算交集
            counter = Counter()
            for i in iss:
                counter[source[i]] += 1
            for i in iss:
                if counter[target[i]] > 0:
                    t += 1
                    counter[target[i]] -= 1
        return n - t