### Ý TƯỞNG
**Ta có nhận xét rằng:**
> Chuỗi $a$ bé hơn chuỗi $b$ khi ở vị trí $i$ đầu tiên mà $a[i] \neq b[i]$ thì $a[i] < b[i]$
**Nên ta xét các cặp chuỗi**
- Ta xác định vị trí $i$ đầu tiên mà $a[i] \neq b[i]$
- Từ đó ta xác định kí tự $a[i]$ đứng trước kí tự ở chuỗi $b[i]$
**Từ đó, ta quy về bài toán**
> Cho 26 chữ cái và các ràng buộc `u v` với ý nghĩa chữ cái `u` đứng trước chữ cái `v`.
> **Yêu cầu:** Hãy sắp xếp lại các chữ cái sao cho thoả các ràng buộc trên
- Ta coi các chữ cái là các đỉnh và các mối quan hệ `u v` là các cạnh một chiều từ `u` đến `v`
- Sau đó ta dùng sắp xếp tô-pô để sắp xếp lại các chữ cái
### CODE THAM KHẢO
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxN = 200;
int n, disc,
vis[100];
string inp[maxN + 1];
set <int> w[100];
vector <int> tp;
void makeEdge(string a, string b){
int lim = min(a.size(), b.size());
for (int i = 0; i < lim; i++){
if (a[i] != b[i]){
w[a[i] - 'a'].insert(b[i] - 'a');
return;
}
}
}
void dfs(int u){
vis[u] = 1;
for (int v: w[u]){
if (!vis[v])
dfs(v);
if (vis[v] == 1){
cout<<-1;
exit(0);
}
}
tp.push_back(u);
vis[u] = 2;
}
void init(){
cin>>n;
for (int i = 1; i <= n; i++){
cin>>inp[i];
if (i > 1){
makeEdge(inp[i - 1], inp[i]);
}
}
}
void solve(){
for (int i = 0; i < 26; i++)
if (!vis[i])
dfs(i);
reverse(tp.begin(), tp.end());
for (int u: tp)
cout<<char(u + 'a');
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
init(); solve();
}
```
minhpnk2
Created at
0 likes