Advertisement
Josif_tepe

Untitled

Aug 19th, 2023
894
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.06 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <vector>
  5. #include <set>
  6. #include <map>
  7. #include <fstream>
  8. #include <queue>
  9. #include <stack>
  10. using namespace std;
  11. const int maxn = 2e5 + 10;
  12. vector<int> graph[maxn], rev_graph[maxn];
  13. stack<int> st;
  14. bool visited[maxn];
  15. vector<int> cycle;
  16. void topological_sort(int node) {
  17.     visited[node] = true;
  18.     for(int i = 0; i < (int) graph[node].size(); i++) {
  19.         int neighbour = graph[node][i];
  20.         if(!visited[neighbour]) {
  21.             topological_sort(neighbour);
  22.         }
  23.     }
  24.     st.push(node);
  25. }
  26. void dfs(int node) {
  27.     visited[node] = true;
  28.     cycle.push_back(node);
  29.     for(int i = 0; i < (int) rev_graph[node].size(); i++) {
  30.         int neighbour = rev_graph[node][i];
  31.         if(!visited[neighbour]) {
  32.             dfs(neighbour);
  33.         }
  34.     }
  35. }
  36. int main() {
  37.     ios_base::sync_with_stdio(false);
  38.     int t;
  39.     cin >> t;
  40.    
  41.     while(t--) {
  42.         int n;
  43.         cin >> n;
  44.         vector<pair<int, int> > edges;
  45.         for(int i = 0; i < n; i++) {
  46.             int node;
  47.             cin >> node;
  48.             node--;
  49.             graph[i].push_back(node);
  50.             rev_graph[node].push_back(i);
  51.             edges.push_back({i, node});
  52.         }
  53.         memset(visited, false, sizeof visited);
  54.         for(int i = 0; i < n; i++) {
  55.             if(!visited[i]) {
  56.                 topological_sort(i);
  57.             }
  58.         }
  59.         memset(visited, false, sizeof visited);
  60.         string result = "A";
  61.         int cycles_with_length_of_2 = 0;
  62.         vector<int> cycles_nodes;
  63.         while(!st.empty()) {
  64.             int node = st.top();
  65.             st.pop();
  66.             if(!visited[node]) {
  67.                 cycle.clear();
  68.                 dfs(node);
  69.                 if(cycle.size() > 2) {
  70.                     result = "B";
  71.                     break;
  72.                 }
  73.                 if(cycle.size() == 2) {
  74.                     cycles_with_length_of_2++;
  75.                     cycles_nodes = cycle;
  76.                 }
  77.             }
  78.         }
  79.        
  80.         for(int i = 0; i < n; i++) {
  81.             graph[i].clear();
  82.             rev_graph[i].clear();
  83.         }
  84.         while(!st.empty()) {
  85.             st.pop();
  86.         }
  87.         if(cycles_with_length_of_2 > 1) {
  88.             result = "A";
  89.         }
  90.         else if(cycles_with_length_of_2 == 1){
  91.             result = "BOTH";
  92. //            cout << cycles_nodes[0] << " " << cycles_nodes[1] << endl;
  93.             for(int i = 0; i < n; i++) {
  94.                 if(cycles_nodes[0] == edges[i].first and cycles_nodes[1] == edges[i].second) continue;
  95.                 if(cycles_nodes[1] == edges[i].first and cycles_nodes[0] == edges[i].second) continue;
  96.                
  97.                 if(edges[i].second == cycles_nodes[0] or edges[i].second == cycles_nodes[1]) {
  98.                     result = "BOTH";
  99.                 }
  100.                 else {
  101.                     result = "A";
  102.                     break;
  103.                 }
  104.             }
  105.         }
  106.         cout << result << "\n";
  107.     }
  108.     return 0;
  109. }
  110.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement