aaa 数组和 bbb 数组都有 nnn 个数,并且它们都是 nnn 的排列。若每次可以交换 aaa 中任意的两个数,求将 aaa 变成 bbb 的最小交换次数。
例如 a=[4,2,3,1],b=[1,2,3,4]a = [4,2,3,1],b = [1,2,3,4]a=[4,2,3,1],b=[1,2,3,4],将 a0=4a_0=4a0=4 与 a3=1a_3 = 1a3=1 交换,得到 bbb 数组。于是最小交换次数为 111。
这个基本模型的一个通用解法是:建立一张 nnn 个点的图,对于 o≤i≤n−1o \le i \le n - 1o≤i≤n−1,建立无向边 ai,bia_i,b_iai,bi。那么最小交换次数就是 n−cn-cn−c,其中 ccc 表示这个图中连通块的个数。
哪位大佬可以给出这个解法的解释与证明?谢谢!