mickypinata

KOI: Cecil

Dec 6th, 2021 (edited)
567
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 100 + 5;
  5.  
  6. set<int> adj[26];
  7. string str[N];
  8. int inDeg[26];
  9.  
  10. int main(){
  11.  
  12.     int n;
  13.     scanf("%d", &n);
  14.     for(int i = 1; i <= n; ++i){
  15.         cin >> str[i];
  16.     }
  17.     for(int i = 1; i <= n - 1; ++i){
  18.         for(int j = i + 1; j <= n; ++j){
  19.             int len = min(str[i].size(), str[j].size());
  20.             for(int k = 0; k < len; ++k){
  21.                 if(str[i][k] != str[j][k]){
  22.                     int u = str[i][k] - 'a';
  23.                     int v = str[j][k] - 'a';
  24.                     if(adj[u].insert(v).second){
  25.                         ++inDeg[v];
  26.                     }
  27.                     break;
  28.                 }
  29.             }
  30.         }
  31.     }
  32.     priority_queue<int, vector<int>, greater<int>> pq;
  33.     for(int i = 0; i < 26; ++i){
  34.         if(inDeg[i] == 0){
  35.             pq.push(i);
  36.         }
  37.     }
  38.     string ans;
  39.     while(!pq.empty()){
  40.         int u = pq.top();
  41.         pq.pop();
  42.         ans.push_back((char)(u + 'a'));
  43.         for(int v : adj[u]){
  44.             --inDeg[v];
  45.             if(inDeg[v] == 0){
  46.                 pq.push(v);
  47.             }
  48.         }
  49.     }
  50.     if(ans.size() < 26){
  51.         cout << "-1";
  52.     } else {
  53.         cout << ans;
  54.     }
  55.  
  56.     return 0;
  57. }
  58.  
  59. // Rework: O(N^2) Solution
  60. #include <bits/stdc++.h>
  61. using namespace std;
  62.  
  63. const int N = 100 + 5;
  64.  
  65. vector<int> adj[26];
  66. string str[N];
  67. int inDeg[26];
  68.  
  69. int main(){
  70.  
  71.     int n;
  72.     scanf("%d", &n);
  73.     for(int i = 1; i <= n; ++i){
  74.         cin >> str[i];
  75.     }
  76.     for(int i = 1; i < n; ++i){
  77.         int j = i + 1;
  78.         int len = min(str[i].size(), str[j].size());
  79.         for(int k = 0; k < len; ++k){
  80.             if(str[i][k] != str[j][k]){
  81.                 char u = str[i][k] - 'a';
  82.                 char v = str[j][k] - 'a';
  83.                 adj[u].push_back(v);
  84.                 ++inDeg[v];
  85.                 break;
  86.             }
  87.         }
  88.     }
  89.     priority_queue<int, vector<int>, greater<int>> pq;
  90.     string ans;
  91.     for(int u = 0; u < 26; ++u){
  92.         if(inDeg[u] == 0){
  93.             pq.push(u);
  94.         }
  95.     }
  96.     while(!pq.empty()){
  97.         int u = pq.top();
  98.         pq.pop();
  99.         ans.push_back((char)(u + 'a'));
  100.         for(int v : adj[u]){
  101.             if(--inDeg[v] == 0){
  102.                 pq.push(v);
  103.             }
  104.         }
  105.     }
  106.     if(ans.size() < 26){
  107.         cout << "-1";
  108.     } else {
  109.         cout << ans;
  110.     }
  111.  
  112.     return 0;
  113. }
  114.  
RAW Paste Data Copied