题解：SP28 HMRO - Help the Military Recruitment Office!

题意

已知

n

个人的 PIESL 码和所属的 MRO。将

m

个 MRO 替换为新的 MRO。询问

t

次，输出询问的 MRO。

思路

按照题目模拟。使用两个 map<string,string> 分别为 m1 和 fa.

m1 存储每个人的 PIESL 和旧的 MRO。
fa 存储旧的 MRO 和新的 MRO。

使用并查集进行优化。

代码

CPP

#include<bits/stdc++.h>
#define int long long

using namespace std;

int T, n, m, t;
map<string, string> m1, fa;
string findfa(string x) {
	return fa[x] = (fa[x] == x ? x : findfa(fa[x]));
}
signed main() {
	cin.tie(0), cout.tie(0);
	cin >> T;
	while (T--) {
		m1.clear(), fa.clear();

		cin >> n;
		for (int i = 1; i <= n; i++) {
			string PIESL, MRO;
			cin >> PIESL >> MRO;
			m1[PIESL] = MRO;
			fa[MRO] = MRO;
		}
		cin >> m;
		for (int i = 1; i <= m; i++) {
			string Old, New;
			cin >> Old >> New;
			fa[findfa(Old)] = findfa(New);
		}
		cin >> t;
		for (int i = 1; i <= t; i++) {
			string q;
			cin >> q;
			cout << q << " " <<	findfa(m1[q]) << "\n";
		}
	}
	return 0;
}

附上 AC 记录

题解：SP28 HMRO - Help the Military Recruitment Office!

文章操作

题意

思路

代码

相关推荐

评论

题解：SP28 HMRO - Help the Military Recruitment Office!