本蒟蒻去 SPOJ 不知道怎样注册,请大佬们求救!
#include <iostream>
#include <vector>
#include <cstring>
#include <string.h>
#include <string>
#define then ,
using namespace std;
const int kMaxN(30);
int indeg[kMaxN], outdeg[kMaxN], vis[kMaxN], t, n, cnt, num, x, y, sum1, sum2;
bool use[kMaxN], ans, flag;
vector<int> e[kMaxN];
string s;
void init(void) {
for (int i = 0; i < kMaxN; ++i) {
e[i].clear();
}
num = 0;
cnt = 0;
fill(indeg, indeg + 29, 0);
fill(outdeg, outdeg + 29, 0);
fill(vis, vis + 29, 0);
fill(use, use + 29, 0);
}
bool dfs(int x) {
cnt++;
use[x] = true;
if (cnt == num) {
return true;
}
bool b = false;
for (int i = 0; i < e[x].size(); ++i) {
int tmp = e[x][i];
if (!use[tmp]) {
b |= dfs(tmp);
}
}
return b;
}
int main(int argc, char *argv[]) {
for (cin >> t; t--;) {
init();
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> s;
x = s[0] - 'a' + 1;
y = s[s.size() - 1] - 'a' + 1;
e[x].push_back(y);
e[y].push_back(x);
num += (vis[x] == 0);
vis[x] = true;
num += (vis[y] == 0);
vis[y] = true;
indeg[y]++ then outdeg[x]++;
}
ans = false;
for (int i = 1; i <= 26; ++i) {
if (e[i].size()) {
ans = dfs(i);
break;
}
}
if (!ans) {
cout << "The door cannot be opened." << '\n';
continue;
}
sum1 = sum2 = 0;
flag = true;
for (int i = 1; i <= 26; ++i) {
if (indeg[i] == outdeg[i]) {
continue;
} else if (indeg[i] - outdeg[i] == 1 && sum1 == 0) {
sum1 ++;
} else if (indeg[i] - outdeg[i] == -1 && sum2 == 0) {
sum2++;
} else {
flag = false;
break;
}
}
if (flag) {
cout << "Ordering is possible." << '\n';
} else {
cout << "The door cannot be opened." << '\n';
}
}
return 0;
}