#include <bits/stdc++.h>
using namespace std;
const int md = 105;
const int oo = 1e9;
int low[md], num[md], a[md], ans[md];
stack < int > st;
vector < int > adj[md], topo;
int cnt, n;
string s1[md], s[md];
void tarjan(int u) {
st.push(u);
low[u] = num[u] = ++cnt;
for(int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i];
if (num[v])
low[u] = min(low[u], num[v]);
else {
tarjan(v);
low[u] = min(low[u], low[v]);
}
}
if (low[u] == num[u]) {
int v = 0, c = 0;
do {
v = st.top(); st.pop();
c++;
low[u] = num[u] = oo;
} while (v != u);
if (c >= 2) {
cout << "NE";
exit(0);
}
}
topo.push_back(u);
}
int main() {
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin >> n;
for(int i = 1; i <= n; i++)
cin >> s1[i];
for(int i = 1; i <= n; i++) {
int x;
cin >> x;
s[i] = s1[x];
}
//for(int i = 1; i <= n; i++)
// cout << s[i] << endl;
for(int u = 1; u < n; u++) {
//int u = a[i];
//cerr << s[u] << endl;
int v = u + 1;
//for(int v = u + 1; v <= n; v++) {
int len = min(s[u].size(), s[v].size());
//cerr << s[v] << " ";
bool ok = false;
for(int k = 0; k < len; k++)
if (s[u][k] != s[v][k]) {
ok = true;
//cout << s[u][k] - 'a' << " " << s[v][k] - 'a' << endl;
adj[s[v][k] - 'a'].push_back(s[u][k] - 'a');
break;
}
if (ok == false && s[u].size() > s[v].size()) {
cout << "NE";
return 0;
}
//cerr << endl;
}
//cerr << "checking";
for(int i = 0; i < 26; i++) {
//cerr << adj[i].size() << endl;
if (!num[i])
tarjan(i);
/*cerr << char(i + 'a') << ": ";
for(int j = 0; j < 26; j++) {
cerr << (num[j] != 0) << " ";
}*/
/*cerr << endl;
for(int j = 0; j < topo.size(); j++)
cerr << char(topo[j] + 'a') << " ";
cerr << "\n";*/
}
int cnt = 0;
for(int i = 0; i < topo.size(); i++) {
//cout << topo[i] << " ";
ans[topo[i]] = cnt++;
}
cout << "DA\n";
for(int i = 0; i < 26; i++)
cout << char(ans[i] + 'a');
/*cout << endl;
for(int i = 'a'; i <= 'z'; i++)
cout << char(i);*/
return 0;
}
Compilation message
cezar.cpp: In function 'void tarjan(int)':
cezar.cpp:17:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[u].size(); i++) {
~~^~~~~~~~~~~~~~~
cezar.cpp: In function 'int main()':
cezar.cpp:91:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < topo.size(); i++) {
~~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
380 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
