Advertisement
Guest User

Untitled

a guest
Sep 24th, 2017
51
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<map>
  3. #include<vector>
  4. #include<stack>
  5. #include<algorithm>
  6. #include<cmath>
  7. #include<set>
  8. #include<iomanip>
  9. #include<fstream>
  10.  
  11. using namespace std;
  12.  
  13. int t = 0;
  14.  
  15. void dfs (vector<set<int>> &g, vector<bool> &used, vector<int> &tin, int v, bool &p) {
  16.     used[v] = true;
  17.     tin[v] = t++;
  18.     for(auto u = g[v].begin(); u != g[v].end(); u++) {
  19.         cout << v << ' ' << used.size() << ' ' << *u << endl;
  20.         if(!used[*u])
  21.             dfs(g, used, tin, *u, p);
  22.         p = false;
  23.     }
  24. }
  25.  
  26. int main() {
  27.     ifstream in("fortification.in");
  28.     ofstream out("fortification.out");
  29.    
  30.     int n;
  31.     cin >> n;
  32.     vector<string> inp(n);
  33.    
  34.     for(int i = 0; i < n; i++) {
  35.         cin >> inp[i];
  36.         string s = "";
  37.         for(int j = 0; j < 10 - inp[i].length() + 1; j++)
  38.             s += 'x';
  39.         s += inp[i];
  40.         inp[i] = s;
  41.     }
  42.    
  43.     vector<set<int>> g(10);
  44.    
  45.     for(int i = 0; i < n; i++) {
  46.         for(int j = i + 1; j < n; j++) {
  47.             int c = 0;
  48.             while(c < 10 && inp[i][c] == inp[j][c])
  49.                 c++;
  50.             if(c < 11) {
  51.                 g[inp[j][c] - 'a'].insert(inp[i][c] - 'a');
  52.             }
  53.         }
  54.     }
  55.    
  56.     vector<bool> used(10, false);
  57.     vector<int> tin(10);
  58.     bool p = true;
  59.     for(int i = 0; i < 10; i++) {
  60.         if(!used[i]) {
  61.             dfs(g, used, tin, i, p);
  62.         }
  63.     }
  64.    
  65.     if(p) {
  66.         cout << "Yes" << endl;
  67.         for(int k : tin)
  68.             cout << k << ' ';
  69.         cout << endl;
  70.     }
  71.     else
  72.         cout << "No" << endl;
  73.    
  74.     return 0;
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement