ccbeginner

UVa Q200

Feb 25th, 2020
107
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //UVa Q200
  2. /******************************************************************************
  3.  
  4.                               Online C++ Compiler.
  5.                Code, Compile, Run and Debug C++ program online.
  6. Write your code in this editor and press "Run" button to compile and execute it.
  7.  
  8. *******************************************************************************/
  9.  
  10. #include <bits/stdc++.h>
  11. using namespace std;
  12.  
  13. bool rec[26][26];//arr[a][b] := a > b
  14. vector<int> v[26];
  15. bool used[26];
  16. void func(string s1, string s2){
  17.     for(unsigned i = 0; i < min(s1.size(), s2.size()); ++i){
  18.         used[s1[i] - 'A'] = used[s2[i] - 'A'] = 1;
  19.         if(s1[i] == s2[i])continue;
  20.         if(!rec[s1[i] - 'A'][s2[i] - 'A'])v[s1[i] - 'A'].emplace_back(s2[i] - 'A');
  21.         rec[s1[i] - 'A'][s2[i] - 'A'] = 1;
  22.         break;
  23.     }
  24. }
  25.  
  26. vector<int> ans;
  27. int n;
  28. void dfs(int u){
  29.     ans.emplace_back(u);
  30.     if(ans.size() == n)return;
  31.     for(unsigned i = 0; i < v[u].size(); ++i){
  32.         dfs(v[u][i]);
  33.         if(ans.size() == n)return;
  34.     }
  35.     ans.pop_back();
  36. }
  37.  
  38. int main(){
  39.     string s[2];
  40.     cin >> s[1];
  41.     bool b = 0;
  42.     while(cin >> s[b]){
  43.         if(s[b] == "#")break;
  44.         func(s[!b], s[b]);
  45.         b = !b;
  46.     }
  47.     for(int i = 0; i < 26; ++i)if(used[i])++n;
  48.     for(int i = 0; i < 26; ++i){
  49.         if(used[i])dfs(i);
  50.         if(ans.size() == n)break;
  51.     }
  52.     for(int i = 0; i < ans.size(); ++i){
  53.         cout << char(ans[i]+'A');
  54.     }
  55.     cout << '\n';
  56.     return 0;
  57. }
RAW Paste Data