#include<iostream> #include<string> #include<cstdio> #include<cstring> #include<cstdlib> using namespace std; int T, n; int match[30][30]; int temp[30][30]; void dfs(int pos) { for(int i = 0; i < 26; i++) if(temp[pos][i]) { temp[pos][i] -= 1; dfs(i); } } int main() { cin >> T; while(T--) { memset(match, 0, sizeof(match)); cin >> n; for(int i = 0; i < n; i++) { string in; cin >> in; match[in[0] - 'a'][in[in.size() - 1] - 'a'] += 1; } bool ok = true; for(int i = 0; i < 26; i++) { memcpy(temp, match, sizeof(match)); dfs(i); ok = true; for(int i = 0; i < 30; i++)#include<iostream> #include<string> #include<cstdio> #include<cstring> #include<cstdlib> using namespace std; int T, n; int match[30][30]; int temp[30][30]; void dfs(int pos) { for(int i = 0; i < 26; i++) if(temp[pos][i]) { temp[pos][i] -= 1; dfs(i); } } int main() { cin >> T; while(T--) { memset(match, 0, sizeof(match)); cin >> n; for(int i = 0; i < n; i++) { string in; cin >> in; match[in[0] - 'a'][in[in.size() - 1] - 'a'] += 1; } bool ok = true; for(int i = 0; i < 26; i++) { memcpy(temp, match, sizeof(match)); dfs(i); ok = true; for(int i = 0; i < 30; i++) for(int j = 0; j < 30; j++) if(temp[i][j]) ok = false; if(ok) break; } if(ok) cout << "Ordering is possible." << endl; else cout << "The door cannot be opened." << endl; } } for(int j = 0; j < 30; j++) if(temp[i][j]) ok = false; if(ok) break; } if(ok) cout << "Ordering is possible." << endl; else cout << "The door cannot be opened." << endl; } }
欧拉道路,给一系列的单词判断是否首尾单词相同,建立数组match用来存储26个英文字母的首尾出现次数,比如acm则match[0][13]就加一,如果可以形成欧拉道路的话则
经过dfs处理如果可以形成欧拉通路的话,则match中的数据都应该变为0,若不为0的话则无法形成欧拉道路。