思路

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

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

C++

#include <bits/stdc++.h>
using namespace std;

// 并查集
struct DSU {
	vector<int> p, r;
	DSU(int n = 0) { init(n); }
	void init(int n) {
		p.resize(n);
		r.assign(n, 0);
		iota(p.begin(), p.end(), 0);
	}
	int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
	bool unite(int a, int b) {
		a = find(a); b = find(b);
		if (a == b) return false;
		if (r[a] < r[b]) swap(a, b);
		p[b] = a;
		if (r[a] == r[b]) r[a]++;
		return true;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T; 
	if (!(cin >> T)) return 0;
	while (T--) {
		int n; long long m;
		cin >> n >> m; // m 不直接使用
		vector<int> a(n), b(n);
		for (int i = 0; i < n; ++i) cin >> a[i];
		for (int i = 0; i < n; ++i) cin >> b[i];

		// 收集出现的所有值并排序去重（坐标压缩）
		vector<int> vals; 
		vals.reserve(2 * n);
		for (int i = 0; i < n; ++i) {
			vals.push_back(a[i]);
			vals.push_back(b[i]);
		}
		sort(vals.begin(), vals.end());
		vals.erase(unique(vals.begin(), vals.end()), vals.end());
		int K = (int)vals.size();

		// 将值映射到 0..K-1
		auto getId = [&](int x) {
			int idx = int(lower_bound(vals.begin(), vals.end(), x) - vals.begin());
			return idx;
		};

		// 并查集合并每条边 (a_i, b_i)
		DSU dsu(K);
		for (int i = 0; i < n; ++i) {
			int u = getId(a[i]);
			int v = getId(b[i]);
			dsu.unite(u, v);
		}

		// 统计连通块个数 C
		int C = 0;
		for (int i = 0; i < K; ++i) if (dsu.find(i) == i) ++C;

		// 答案 = K - C
		cout << (K - C) << '\n';
	}
	return 0;
}

Python

import sys

# 并查集
class DSU:
    def __init__(self, n):
        self.p = list(range(n))
        self.r = [0]*n
    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]
    def unite(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.r[a] < self.r[b]:
            a, b = b, a
        self.p[b] = a
        if self.r[a] == self.r[b]:
            self.r[a] += 1
        return True

data = sys.stdin.read().strip().split()
it = iter(data)
T = int(next(it))
out_lines = []
for _ in range(T):
    n = int(next(it)); m = int(next(it))  # m 不直接使用
    a = [int(next(it)) for _ in range(n)]
    b = [int(next(it)) for _ in range(n)]

    # 坐标压缩
    vals = sorted(set(a + b))
    idx = {v:i for i, v in enumerate(vals)}
    K = len(vals)

    dsu = DSU(K)
    for i in range(n):
        u = idx[a[i]]
        v = idx[b[i]]
        dsu.unite(u, v)

    C = sum(1 for i in range(K) if dsu.find(i) == i)
    out_lines.append(str(K - C))

sys.stdout.write("\n".join(out_lines))

Java

import java.io.*;
import java.util.*;

// 并查集
class DSU {
	int[] p, r;
	DSU(int n) {
		p = new int[n];
		r = new int[n];
		for (int i = 0; i < n; i++) p[i] = i;
	}
	int find(int x) {
		if (p[x] != x) p[x] = find(p[x]);
		return p[x];
	}
	boolean unite(int a, int b) {
		a = find(a); b = find(b);
		if (a == b) return false;
		if (r[a] < r[b]) { int t = a; a = b; b = t; }
		p[b] = a;
		if (r[a] == r[b]) r[a]++;
		return true;
	}
}

public class Main {
	static class FastScanner {
		BufferedInputStream in;
		byte[] buffer = new byte[1 << 16];
		int ptr = 0, len = 0;
		FastScanner(InputStream is) { in = new BufferedInputStream(is); }
		int read() throws IOException {
			if (ptr >= len) {
				len = in.read(buffer);
				ptr = 0;
				if (len <= 0) return -1;
			}
			return buffer[ptr++];
		}
		int nextInt() throws IOException {
			int c, s = 1, x = 0;
			do { c = read(); } while (c <= ' ' && c != -1);
			if (c == '-') { s = -1; c = read(); }
			for (; c > ' '; c = read()) x = x * 10 + (c - '0');
			return x * s;
		}
	}
	public static void main(String[] args) throws Exception {
		FastScanner fs = new FastScanner(System.in);
		StringBuilder sb = new StringBuilder();
		int T = fs.nextInt();
		while (T-- > 0) {
			int n = fs.nextInt();
			int m = fs.nextInt(); // m 不直接使用
			int[] a = new int[n], b = new int[n];
			for (int i = 0; i < n; i++) a[i] = fs.nextInt();
			for (int i = 0; i < n; i++) b[i] = fs.nextInt();

			// 坐标压缩：排序去重 + 二分
			int[] vals = new int[2 * n];
			for (int i = 0; i < n; i++) {
				vals[2*i] = a[i];
				vals[2*i + 1] = b[i];
			}
			Arrays.sort(vals);
			int k = 0;
			for (int i = 0; i < vals.length; i++) {
				if (i == 0 || vals[i] != vals[i - 1]) vals[k++] = vals[i];
			}
			int K = k;
			DSU dsu = new DSU(K);

			// 辅助函数：二分找到值的下标
			for (int i = 0; i < n; i++) {
				int u = Arrays.binarySearch(vals, 0, K, a[i]);
				int v = Arrays.binarySearch(vals, 0, K, b[i]);
				dsu.unite(u, v);
			}

			int C = 0;
			for (int i = 0; i < K; i++) if (dsu.find(i) == i) C++;
			sb.append(K - C).append('\n');
		}
		System.out.print(sb.toString());
	}
}

题目内容

多多有两个长度为 $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$ 。

输出描述

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

样例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]$ 。