Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- void allTopologicalSort(vector<char> &cur, int *cnt, unordered_map<char, bool> &visited,
- unordered_map<char, int> &inDegree, unordered_map<char, vector<char>> &adj)
- {
- bool flag = false;
- for (auto [ch, vec] : adj)
- {
- if (inDegree[ch] == 0 && visited[ch] == false)
- {
- for (auto nei : adj[ch])
- {
- inDegree[nei]--;
- }
- cur.push_back(ch);
- visited[ch] = true;
- allTopologicalSort(cur, cnt, visited, inDegree, adj);
- ;
- visited[ch] = false;
- cur.erase(cur.end() - 1);
- for (auto nei : adj[ch])
- {
- inDegree[nei]--;
- }
- flag = true;
- }
- }
- if (flag == false)
- {
- (*cnt)++;
- }
- }
- string LineOrdering(vector<string> &inputs)
- {
- unordered_map<char, vector<char>> adj;
- unordered_map<char, int> inDegree;
- for (string input : inputs)
- {
- if (input[1] == '>')
- {
- adj[input[0]].push_back(input[2]);
- inDegree[input[2]]++;
- }
- else
- {
- adj[input[2]].push_back(input[0]);
- inDegree[input[0]]++;
- }
- }
- unordered_map<char, bool> visited;
- for (auto [ch, vec] : adj)
- {
- visited[ch] = false;
- }
- int cnt = 0;
- vector<char> cur;
- allTopologicalSort(cur, &cnt, visited, inDegree, adj);
- return to_string(cnt);
- }
- int main()
- {
- int n;
- cin >> n;
- vector<string> inputs(n);
- for (int i = 0; i < n; i++)
- {
- cin >> inputs[i];
- }
- cout << LineOrdering(inputs) << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement