自动搬运

查看原文

来自洛谷，原作者为

	yangjinqian 壶关条件：橙名+/绿勾+/等级分800+,要私，关系户绿名+|不拿蓝勾不改签

搬运于2025-08-24 22:25:19，当前版本为作者最后更新于2024-08-25 13:21:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意：

给出 $m$ 种字母转换关系，再有 $n$ 个询问，判断给定的字符串 $s$ 是否能转换成字符串 $t$ 。

思路：

用 map 把每种字母转换关系映射进来，由于一个字符可能会有多种转换关系，所以 map 定义的第二个要写成 vector<char> 。

接下来判断的时候，先判断两个字符串长度是否相等，否则输出 no ，是则循环 dfs 。

dfs 的时候可以用一个变量记录是否转换到当前字符，别忘了还有一个标记数组。而当前字符如果为 char(0) 就是递归边界。接下来就枚举 map 里的 vector 每次只要当前要转换的字符没被标记过就 dfs 这个字符。

参考文献

dfs:

void dfs(char x, char y){
	if (x == y){
		flag = 1;
		return;
	}
	v[int(x)] = 1;
	if (x == char(0)) return;
	for (int i = 0; i < a[x].size(); i++)
		if (!v[int(a[x][i])])
			dfs(a[x][i], y);
}

map 定义： map<char, vector<char>> a;

最终代码

#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int n, m;
bool flag = 0;
string s1, s2;
int v[N];
map<char, vector<char>> a;
void dfs(char x, char y){
	if (x == y){
		flag = 1;
		return;
	}
	v[int(x)] = 1;
	if (x == char(0)) return;
	for (int i = 0; i < a[x].size(); i++)
		if (!v[int(a[x][i])])
			dfs(a[x][i], y);
}
int main(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		char b, c;
		cin >> b >> c;
		a[b].push_back(c);
	}
	while (m--){
		cin >> s1 >> s2;
		if (s1.size() != s2.size()){
			cout << "no" << endl;
			continue;
		}
		bool k = 0;
		for (int i = 0; i < s1.size(); i++)
			if (s1[i] != s2[i]){
				dfs(s1[i], s2[i]);
				if (!flag) k = 1;
				flag = 0;
				memset(v, 0, sizeof v);
			}
		if (!k) cout << "yes";
		else cout << "no";
		puts("");
	}
	return 0;
}