Advertisement
Guest User

Untitled

a guest
May 23rd, 2018
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.49 KB | None | 0 0
  1. # include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<pair<int, int> >  v[200000];
  5. vector<pair<int, char> > g[100010];
  6. queue<char> q;
  7. int us[200000], used[100010], check[200010];
  8. bool here[200100];
  9. int kol[200000];
  10. string s[200010];
  11. char p[200010];
  12.  
  13. void dfs(char x){
  14.  
  15.     check[x] = 1;
  16.  
  17.     for(pair<int, char> i : g[x]){
  18.         if(check[i.second] == 0 && kol[i.first] == 0){
  19.             dfs(i.second);
  20.         }
  21.     }
  22.  
  23. }
  24.  
  25. int main()
  26. {
  27.     ios_base::sync_with_stdio(0);
  28.     cin.tie(0);
  29.     cout.tie(0);
  30.     freopen("useless.out", "w", stdout);
  31.     freopen("useless.in", "r", stdin);
  32.     int n, m, k = 0;
  33.     char c;
  34.     cin>> n>> c;
  35.     here[c] = true;
  36.     while(cin>> s[++k]){}
  37.     k--;
  38.     n = k;
  39.     for(int i = 1; i <= n ;i ++){
  40.         if(s[i] == "->"){
  41.             used[i - 1] = 1;
  42.             used[i] = -1;
  43.         }
  44.     }
  45.  
  46.     for(int i = 1; i <= n; i ++){
  47.         if(used[i] == 0){
  48.             used[i - 2] = 2;
  49.         }
  50.     }
  51.     k = 0;
  52.     for(int i = 1; i <= n; i ++){
  53.         if(used[i] == 1){
  54.             k++;
  55.             p[k] = s[i][0];
  56.             s[k] = "";
  57.         } else if(used[i]  == 2){
  58.             k++;
  59.             p[k] = s[i][0];
  60.             s[k] = s[i + 2];
  61.         }
  62.     }
  63.  
  64.     n = k;
  65.  
  66.     for(int i = 1; i <= n; i ++){
  67.         bool good = false;
  68.  
  69.  
  70.         here[p[i]] = true;
  71.         for(int j = 0; j < s[i].size(); j ++){
  72.             if(s[i][j] >= 'A' && s[i][j] <= 'Z'){
  73.                 here[s[i][j]] = true;
  74.                 g[p[i]].push_back(make_pair(i, s[i][j]));
  75.                 good = true;
  76.                 kol[i] ++;
  77.                 v[s[i][j]].push_back(make_pair(i, j));
  78.             }
  79.         }
  80.         if(!good){
  81.             us[p[i]] = 1;
  82.             q.push(p[i]);
  83.         }
  84.     }
  85.     while(!q.empty()){
  86.         char st = q.front();
  87.         q.pop();
  88.         //cout << st<<'\n';
  89.         for(pair<int, int> i : v[st]){
  90.             if(s[i.first][i.second] != '#'){
  91.                 s[i.first][i.second] = '#';
  92.                 kol[i.first]--;
  93.                 if(kol[i.first] == 0 && !us[p[i.first]]){
  94.                     us[p[i.first]] = 1;
  95.                     q.push(p[i.first]);
  96.                 }
  97.             }
  98.         }
  99.     }
  100.    
  101.     dfs(c);
  102.  
  103.  
  104.     for(char i = 'A'; i <= 'Z'; i ++){
  105.         if(check[i] == 0 && here[i]){
  106.             us[i] = 0;
  107.         }
  108.     }
  109.  
  110.     for(char i = 'A'; i <= 'Z'; i ++){
  111.         if(us[i] == 0 && here[i]){
  112.             cout << i<<' ';
  113.         }
  114.     }
  115.  
  116. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement