UVA 1757 - Secret Chamber at Mount Rushmore
Contents
本題為中山大學高等程式設計課程作業指定題目之三星題。
由於這題可能是我課堂報告的題目，所以記錄一下。
題目大意
題目先給予 m 組字母轉換條件，每組會有兩個字母，前面的字母可以視為後面的字母。
再來有 n 個問題，每個問題給兩個字串，問前面的字串是否和後面的字串相等。
輸入範圍
1 <= m <= 500, 1 <= n <= 50，字串皆為小寫英文字母組成，且 1 <= 字串長度 <= 50。
解法
先把題目轉換成有向圖，有 26 個點(小寫字母 a ~ z)，字母轉換條件就是邊。
我選擇使用 vector 紀錄邊、再使用陣列紀錄連通關係。對於每個字母，使用 dfs 紀錄點是否有連通，最後再把每個問題的兩個字串做判斷即可。
要注意的是可能會有字串長度不一樣的問題(其實範測有)。
程式碼
#include <bits/stdc++.h>
using namespace std;
bool connect[26][26];
vector<char>v[26];
void dfs(int parent, int a) {
for(int i=0; i<v[a].size(); i++) {
if (connect[parent][v[a][i]]) continue;
connect[parent][v[a][i]] = true;
dfs(parent, v[a][i]);
}
}
int main() {
int n, m;
while(cin >> n >> m) {
memset(connect, false, sizeof(connect));
for(int i=0; i<26; i++) v[i].clear();
char a, b;
for(int i=0; i<26; i++) connect[i][i] = true;
for(int i=0; i<n; i++) {
cin >> a >> b;
connect[a-'a'][b-'a'] = true;
v[a-'a'].push_back(b-'a');
}
for(int i=0; i<26; i++) {
for(int j=0; j<v[i].size(); j++) {
dfs(i, v[i][j]);
}
}
string s1, s2;
while(m--) {
cin >> s1 >> s2;
bool answer = true;
if (s1.size() != s2.size()) {
cout << "no\n";
continue;
}
for(int i=0; i<s1.size(); i++) {
if (!connect[s1[i]-'a'][s2[i]-'a']) answer = false;
}
cout << (answer ? "yes\n" : "no\n");
}
}
return 0;
}