图建模：对每个位置 $i$ ，连无向边 $(a_i, b_i)$ 。则图的每个连通块中的所有值最终必须被“合并”为同一个值。
关键结论：若某连通块包含 $k$ 个不同值，至少需要 $k-1$ 次操作（每次操作最多将不同值的种类数减少 $1$ ），且可沿生成树依次合并达到该下界。
答案：设 $K$ 为在 $a\cup b$ 中出现的不同值总数， $C$ 为上述图的连通块个数，则最少操作数为 $K - C.$

实现用并查集（DSU）统计出现值的连通块个数即可。注意要把所有出现过的值计入节点，即便某值只与自己相连（如 $a_i=b_i$ ）。

P3536.第4题-多多的两个序列

1000ms

Difficulty: 6

所属公司 : 拼多多

算法与标签>并查集

题目内容

多多有两个长度为 $n$ 的正整数序列 $a,b$ ，序列中的元素值是不超过 $m$ 的正整数，即对于任意 $1≤i≤n$ , 满足 $1 ≤ a_i,b_i ≤ m$ 。

一次操作包括下列步骤：

1.仼选 $x,y$ ，满足 $1≤x,y≤m$ 。

2.对于仼意 $i(1 ≤i≤ n)$ ，如果 $a_i=x$ ，则将 $a_i$ 赋值为 $y$ 。

3.对于仼意 $i(1 ≤i≤ n)$ ，如果 $b_i=x$ ，则将 $b_i$ 赋值为 $y$ 。

可以进行上述操作任意多次，问最少需要多少次操作，可以使得序列 $a$ 与 $b$ 变得完全相同。

第一行为一个整数 $T$ ，表示共有 $T$ 组测试数据 $(1 ≤ T ≤1000)$ 。

接下来每组测试数据，第一行为两个整数 $n,m(1≤n<10^5,1≤m≤10^6)$ 。

第二行为序列 $a$ 中的 $n$ 个正整数，

第三行为序列 $b$ 中的 $n$ 个正整数。

对于 $T$ 组数据， $n$ 的总和不超过 $10^5$ ， $m$ 的总和不超过 $10^6$ 。

对于每组测试数据，在单独的一行里输出所需的最少操作数。

输入

输出

0
1
2

说明

对于第二个数据，可以选取 $x=2,y=5$ ，操作完成后，两个序列都会变成 $[5,5,1]$ 。

对于第三个数据，可以操作两次：

1.选取 $x=2,y=1$ ，操作后， $a=[1,5,1],b=[5,1,1]$ 。

2.选取 $x=1,y=5$ ，操作后， $a=[5,5,5],b=[5,5,5]$ 。

输入

预期输出（选填）