-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathC. Fox And Names_floyd.cpp
55 lines (55 loc) · 1.15 KB
/
C. Fox And Names_floyd.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int LEN = 105;
char arr[N][LEN];
char ret[26];
int e[26][26];
int main(int argc, char const *argv[]) {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
for (int i = 1; i < n; i++) {
int k = 0;
for (; arr[i - 1][k] == arr[i][k]; k++)
;
if (arr[i - 1][k] && arr[i][k]) {
e[arr[i - 1][k] - 'a'][arr[i][k] - 'a'] = 1;
} else if (arr[i - 1][k] && !arr[i][k]) {
cout << "Impossible\n";
exit(0);
}
}
for (int k = 0; k < 26; k++) {
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
e[i][j] |= (e[i][k] & e[k][j]);
}
}
}
for (int i = 0; i < 26; i++) {
if (e[i][i]) {
cout << "Impossible\n";
exit(0);
}
}
for (int i = 0; i < 26; i++) {
ret[i] = char(i + 'a');
}
for (int i = 0; i < 26; i++) {
for (int j = i + 1; j < 26; j++) {
if (e[ret[j] - 'a'][ret[i] - 'a']) {
swap(ret[i], ret[j]);
}
}
}
for (int i = 0; i < 26; i++) {
cout << ret[i];
}
cout << "\n";
return 0;
}