思路
- 图建模：对每个位置 i，连无向边 (ai,bi)。则图的每个连通块中的所有值最终必须被“合并”为同一个值。
- 关键结论：若某连通块包含 k 个不同值，至少需要 k−1 次操作（每次操作最多将不同值的种类数减少 1），且可沿生成树依次合并达到该下界。
- 答案：设 K 为在 a∪b 中出现的不同值总数，C 为上述图的连通块个数，则最少操作数为
K−C.
实现用并查集（DSU）统计出现值的连通块个数即可。注意要把所有出现过的值计入节点，即便某值只与自己相连（如 ai=bi）。
P4372.【并查集4】多多的两个序列
本题为2025年8月31日拼多多机考原题
拼多多机考的介绍点击这里
题目内容
多多有两个长度为 n 的正整数序列 a,b，序列中的元素值是不超过 m 的正整数，即对于任意 1≤i≤n , 满足 1≤ai,bi≤m 。
一次操作包括下列步骤：
1.仼选 x,y ，满足 1≤x,y≤m 。
2.对于仼意 i(1≤i≤n) ，如果 ai=x ，则将 ai 赋值为 y 。
3.对于仼意 i(1≤i≤n) ，如果 bi=x ，则将 bi 赋值为 y 。
可以进行上述操作任意多次，问最少需要多少次操作，可以使得序列 a 与 b 变得完全相同。
输入描述
第一行为一个整数 T ，表示共有 T 组测试数据 (1≤T≤1000) 。
接下来每组测试数据，第一行为两个整数 n,m(1≤n<105,1≤m≤106) 。
第二行为序列 a 中的 n 个正整数，
第三行为序列 b 中的 n 个正整数。
对于 T 组数据， n 的总和不超过 105 ，m 的总和不超过 106 。
输出描述
对于每组测试数据，在单独的一行里输出所需的最少操作数。
样例1
输入
3
3 8
2 5 1
2 5 1
3 8
2 5 1
5 2 1
3 8
2 5 2
5 2 1
输出
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] 。
