给你两个整数数组 source 和 target ,长度都是 n 。还有一个数组 allowedSwaps ,其中每个 allowedSwaps[i] = [ai, bi]
表示你可以交换数组 source 中下标为 ai 和 bi(下标从 0 开始)的两个元素。
注意,你可以按 任意 顺序 多次 交换一对特定下标指向的元素。
相同长度的两个数组 source 和 target 间的 汉明距离 是元素不同的下标数量。形式上,其值等于满足
source[i] != target[i] (下标从 0 开始)的下标 i(0 <= i <= n-1)的数量。
在对数组 source 执行 任意 数量的交换操作后,返回 source 和 target 间的 最小汉明距离 。
(DFS) $O(edges)$
# 连通分量中各个点的值是可以交换的 (可以以任意顺序排序)
# 所以找到连通部分, 把公共元素source== target出现次数加起来即可
def minimumHammingDistance(self, source, target, edges):
res = n = len(source)
G = [set() for i in range(n)]
for i, j in edges:
G[i].add(j)
G[j].add(i)
seen = [0] * n
def dfs(i):
seen[i] = 1
found.append(i)
for j in G[i]:
if not seen[j]:
dfs(j)
for i in range(n):
if seen[i]: continue
found = []
dfs(i)
count1 = collections.Counter(source[j] for j in found)
count2 = collections.Counter(target[j] for j in found)
res -= sum((count1 & count2).values())
return res
ref: lee215