SHARE
TWEET

Untitled

a guest Jul 17th, 2019 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int visited[100005];
  4. int indegree[26];
  5. int exists[26] = {0};
  6. vector<vector<int>> edges;
  7. stack<int> answer;
  8. void dfs(int i)
  9. {
  10.     visited[i] = 1;
  11.     cout << edges[i].size() << endl;
  12.     for(int j = 0;j < edges[i].size();j++)
  13.     {
  14.         if(!visited[edges[i][j]] && exists[edges[i][j]])
  15.             dfs(edges[i][j]);
  16.     }
  17.     answer.push(i);
  18. }
  19. int main()
  20. {
  21.     //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
  22.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  23.     string temp,s;
  24.     cin >> temp;
  25.     edges.assign(30,vector<int>());
  26.     do
  27.     {
  28.         cin >> s;
  29.         if(s!="#")
  30.             for(int i = 0;i < min(s.length(),temp.length());i++)
  31.             {
  32.                 exists[(s[i]-'A')] = 1;
  33.                 exists[(s[i+1]-'A')] = 1;
  34.                 if(s[i] != temp[i])
  35.                 {
  36.                     edges[temp[i]-'A'].push_back(s[i]-'A');
  37.                     indegree[s[i]-'A'] = max(indegree[temp[i]-'A'],indegree[s[i]-'A']+1);
  38.                     break;
  39.                 }
  40.             }
  41.         temp = s;
  42.     } while(s!="#");
  43.     for(int i = 0;i < 26;i++)
  44.         if(exists[i] == 1 && !visited[i] && indegree[i] == 0)
  45.             dfs(i);
  46.     while(!answer.empty())
  47.     {
  48.         cout << (char)(answer.top()+'A');
  49.         answer.pop();
  50.     }
  51.     return 0;
  52. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top