Advertisement
Valkyrie006

Untitled

Dec 3rd, 2021
348
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.76 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void allTopologicalSort(vector<char> &cur, int *cnt, unordered_map<char, bool> &visited,
  5.                         unordered_map<char, int> &inDegree, unordered_map<char, vector<char>> &adj)
  6. {
  7.     bool flag = false;
  8.     for (auto [ch, vec] : adj)
  9.     {
  10.         if (inDegree[ch] == 0 && visited[ch] == false)
  11.         {
  12.             for (auto nei : adj[ch])
  13.             {
  14.                 inDegree[nei]--;
  15.             }
  16.             cur.push_back(ch);
  17.             visited[ch] = true;
  18.             allTopologicalSort(cur, cnt, visited, inDegree, adj);
  19.             ;
  20.  
  21.             visited[ch] = false;
  22.             cur.erase(cur.end() - 1);
  23.  
  24.             for (auto nei : adj[ch])
  25.             {
  26.                 inDegree[nei]--;
  27.             }
  28.  
  29.             flag = true;
  30.         }
  31.     }
  32.  
  33.     if (flag == false)
  34.     {
  35.         (*cnt)++;
  36.     }
  37. }
  38.  
  39. string LineOrdering(vector<string> &inputs)
  40. {
  41.     unordered_map<char, vector<char>> adj;
  42.     unordered_map<char, int> inDegree;
  43.     for (string input : inputs)
  44.     {
  45.         if (input[1] == '>')
  46.         {
  47.             adj[input[0]].push_back(input[2]);
  48.             inDegree[input[2]]++;
  49.         }
  50.         else
  51.         {
  52.             adj[input[2]].push_back(input[0]);
  53.             inDegree[input[0]]++;
  54.         }
  55.     }
  56.  
  57.     unordered_map<char, bool> visited;
  58.     for (auto [ch, vec] : adj)
  59.     {
  60.         visited[ch] = false;
  61.     }
  62.  
  63.     int cnt = 0;
  64.     vector<char> cur;
  65.     allTopologicalSort(cur, &cnt, visited, inDegree, adj);
  66.     return to_string(cnt);
  67. }
  68.  
  69. int main()
  70. {
  71.     int n;
  72.     cin >> n;
  73.     vector<string> inputs(n);
  74.     for (int i = 0; i < n; i++)
  75.     {
  76.         cin >> inputs[i];
  77.     }
  78.     cout << LineOrdering(inputs) << endl;
  79.     return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement