Dang_Quan_10_Tin

RESEARCH

Aug 2nd, 2021 (edited)
221
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5. using ld = long double;
  6. using ull = unsigned long long;
  7.  
  8. template <class T>
  9. void read(T &x)
  10. {
  11.     x = 0;
  12.     register int c;
  13.     while ((c = getchar()) && (c > '9' || c < '0'))
  14.         ;
  15.     for (; c >= '0' && c <= '9'; c = getchar())
  16.         x = x * 10 + c - '0';
  17. }
  18.  
  19. constexpr bool typetest = 0;
  20. constexpr int N = 1e5 + 5;
  21. int n, m, l(0), com[N];
  22. bool ck[N];
  23. string s;
  24. int x[N];
  25. vector<int> adj[N], nadj[N], ss;
  26.  
  27. void Read()
  28. {
  29.     cin >> n >> m >> s;
  30.     s = " " + s;
  31.     for (int i = 1; i <= m; ++i)
  32.     {
  33.         int u, v;
  34.         cin >> u >> v;
  35.         adj[u].emplace_back(v);
  36.         nadj[v].emplace_back(u);
  37.     }
  38. }
  39.  
  40. void dfs(int v)
  41. {
  42.     ck[v] = 1;
  43.     for (auto i : adj[v])
  44.         if (!ck[i])
  45.             dfs(i);
  46.     ss.emplace_back(v);
  47. }
  48.  
  49. void dfs_com(int v)
  50. {
  51.     com[v] = l;
  52.     for (auto i : nadj[v])
  53.         if (!com[i])
  54.             dfs_com(i);
  55. }
  56.  
  57. void Kosaraju()
  58. {
  59.     for (int i = 1; i <= n; ++i)
  60.         if (!ck[i])
  61.             dfs(i);
  62.  
  63.     while (!ss.empty())
  64.     {
  65.         int c = ss.back();
  66.         ss.pop_back();
  67.         if (com[c])
  68.         {
  69.             cout << -1;
  70.             exit(0);
  71.         }
  72.         ++l;
  73.         dfs_com(c);
  74.     }
  75. }
  76.  
  77. int Cal(int v)
  78. {
  79.     queue<int> q[2];
  80.  
  81.     for (int i = 1; i <= n; ++i)
  82.         if ((x[i] = nadj[i].size()) == 0)
  83.         {
  84.             if (s[i] == 'C')
  85.                 q[v].emplace(i);
  86.             else
  87.                 q[s[i] - 'A'].emplace(i);
  88.         }
  89.  
  90.     int ans(0);
  91.  
  92.     for (int turn = v; !q[turn].empty(); turn ^= 1)
  93.     {
  94.         ++ans;
  95.         while (!q[turn].empty())
  96.         {
  97.             int c = q[turn].front();
  98.             q[turn].pop();
  99.  
  100.             for (auto i : adj[c])
  101.             {
  102.                 --x[i];
  103.                 if (x[i] == 0)
  104.                 {
  105.                     if (s[i] == 'C')
  106.                         q[turn].emplace(i);
  107.                     else
  108.                         q[s[i] - 'A'].emplace(i);
  109.                 }
  110.             }
  111.         }
  112.     }
  113.  
  114.     return ans - 1;
  115. }
  116.  
  117. void Solve()
  118. {
  119.     Kosaraju();
  120.     cout << Cal(0);
  121. }
  122.  
  123. int32_t main()
  124. {
  125.     ios::sync_with_stdio(0);
  126.     cin.tie(0);
  127.     cout.tie(0);
  128.     int t(1);
  129.     if (typetest)
  130.         cin >> t;
  131.     for (int _ = 1; _ <= t; ++_)
  132.     {
  133.         //cout << "Case #" << _ << "\n";
  134.         Read();
  135.         Solve();
  136.     }
  137. }
RAW Paste Data