传递闭包
如果字母x小于字母y,就将f[x][y] = 1,然后求一遍传递闭包。
如果f[x][x] = 1,就说明有冲突。
否则将原数组按照f[][]规则进行排序,如果排序结果和原数组不一样就说明还是有冲突。
如果没有冲突输出解
时间复杂度:$O(n^3)$
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
int f[N][N];
bool st[N];
int main() {
int n;
cin >> n;
vector<string> s(n), tmp(n);
for(int i = 0;i < n; ++ i) {
cin >> s[i];
tmp[i] = string(s[i]);
}
for(int i = 0;i < n; ++ i) {
for(int j = i + 1;j < n; ++ j) {
int la = s[i].length(), lb = s[j].length();
for(int k = 0;k < la && k < lb; ++ k) {
if(s[i][k] != s[j][k]) {
f[s[i][k] - 'a'][s[j][k] - 'a'] = 1;
break;
}
}
}
}
auto floyd = []() {
for(int k = 0;k < 26; ++ k) {
for(int i = 0;i < 26; ++ i) {
for(int j = 0;j < 26; ++ j) {
f[i][j] |= f[i][k] & f[k][j];
}
}
}
};
auto get_min = []() -> int{
for(int i = 0;i < 26; ++ i) {
bool flag = true;
if(!st[i]) {
for(int j = 0;j < 26; ++ j) {
if(j != i && !st[j] && f[j][i]) {
flag = false;
}
}
if(flag) {
st[i] = true;
return i;
}
}
}
return -1;
};
floyd();
for(int i = 0;i < 26; ++ i) {
if(f[i][i]) {
puts("Impossible");
return 0;
}
}
sort(tmp.begin(), tmp.end(),
[&](auto a, auto b) {
int la = a.length(), lb = b.length();
for(int i = 0;i < la && i < lb; ++ i) {
if(a[i] != b[i]) {
if(f[a[i] - 'a'][b[i] - 'a']) return true;
return false;
}
}
return la < lb;
});
if(tmp != s) {
puts("Impossible");
}
else {
for(int i = 0;i < 26; ++ i) {
printf("%c", get_min() + 'a');
}
}
return 0;
}
拓扑排序
思路和上面一样,只是floyd换成了拓扑排序
时间复杂度:$O(n^3)$
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
int f[N][N];
int din[N], q[N];
bool st[N];
int hh, tt;
void topsort() {
hh = 0, tt = -1;
for(int i = 0;i < 26; ++ i) {
if(din[i] == 0) {
q[ ++ tt] = i;
}
}
while(hh <= tt) {
int t = q[hh ++ ];
for(int i = 0;i < 26; ++ i) {
if(f[t][i]) {
if(-- din[i] == 0) {
q[ ++ tt] = i;
}
}
}
}
}
int main() {
int n;
cin >> n;
vector<string> s(n), tmp(n);
for(int i = 0;i < n; ++ i) {
cin >> s[i];
tmp[i] = string(s[i]);
}
for(int i = 0;i < n; ++ i) {
for(int j = i + 1;j < n; ++ j) {
int la = s[i].length(), lb = s[j].length();
for(int k = 0;k < la && k < lb; ++ k) {
if(s[i][k] != s[j][k]) {
int a = s[i][k] - 'a', b = s[j][k] - 'a';
if(!f[a][b]) din[b] ++ ;
f[a][b] = 1;
break;
}
}
}
}
topsort();
// for(int i = 0;i < 26; ++ i) {
// cout << din[i] << " \n"[i == 25];
// }
if(tt != 25) {
puts("Impossible");
}
else {
sort(tmp.begin(), tmp.end(),
[&](auto a, auto b) {
int la = a.length(), lb = b.length();
for(int i = 0;i < la && i < lb; ++ i) {
if(a[i] != b[i]) {
if(f[a[i] - 'a'][b[i] - 'a']) return true;
return false;
}
}
return la < lb;
});
for(int i = 0;i < n; ++ i) {
if(s[i] != tmp[i]) {
puts("Impossible");
return 0;
}
}
for(int i = 0;i <= tt; ++ i) {
printf("%c", q[i] + 'a');
}
}
return 0;
}