会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
思路
- 图建模：对每个位置 i，连无向边 (ai,bi)。则图的每个连通块中的所有值最终必须被“合并”为同一个值。
- 关键结论：若某连通块包含 k 个不同值，至少需要 k−1 次操作（每次操作最多将不同值的种类数减少 1），且可沿生成树依次合并达到该下界。
- 答案：设 K 为在 a∪b 中出现的不同值总数，C 为上述图的连通块个数，则最少操作数为
K−C.
实现用并查集（DSU）统计出现值的连通块个数即可。注意要把所有出现过的值计入节点，即便某值只与自己相连（如 ai=bi）。
题目内容
多多拿到两条长度同为 k 的正整数列 p,q，两条里每个元素都是不大于 v 的正整数，也就是任意位置 t 都有 1≤pt,qt≤v 。
单次操作由下面几步构成：
1.任意挑出一组 s,d ，满足 1≤s,d≤v 。
2.在每个位置 t(1≤t≤k) 上，只要 pt=s ，就把 pt 改写成 d 。
3.在每个位置 t(1≤t≤k) 上，只要 qt=s ，就把 qt 改写成 d 。
上述操作允许重复执行、不限次数，求至少做几步才能让序列 p 与 q 处处相等。
输入描述
首行给出一个整数 C ，表示一共有 C 组测试 (1≤C≤1000) 。
随后每一组测试，其首行给出两个整数 k,v(1≤k<105,1≤v≤106) 。
次行给出序列 p 里的 k 个正整数，
再次一行给出序列 q 里的 k 个正整数。
这 C 组里， k 的总和至多为 105 ，v 的总和至多为 106 。
输出描述
每一组测试都要在独占的一行写出最少要做的操作次数。
样例1
输入
3
4 10
1 3 5 7
1 3 5 7
4 10
1 3 5 7
3 1 5 7
4 10
1 3 1 4
3 1 2 4
输出
0
1
2
说明
第二组可以把 s=1,d=3 选成操作对象，做完后两条都会变成 [3,3,5,7] 。
第三组可做两步：
1.先把 s=1,d=3 选成对象，做完后 p=[3,3,3,4],q=[3,3,2,4] 。
2.再把 s=2,d=3 选成对象，做完后 p=[3,3,3,4],q=[3,3,3,4] 。
