SHARE
TWEET

Untitled

a guest Apr 21st, 2017 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <unordered_map>
  3. #include <vector>
  4. #include <stack>
  5. using namespace std;
  6.  
  7. typedef vector<int> vi;
  8. typedef vector<vi> vvi;
  9.  
  10. stack<int> S;
  11.  
  12. void scc(vvi& G, vi& N, int u)
  13. {
  14.     N[u] = 1;
  15.     for (int v : G[u])
  16.         if (N[v] == -1)
  17.             scc(G, N, v);
  18.     S.push(u);
  19. }
  20. #include <cassert>
  21. int main()
  22. {
  23.     ios::sync_with_stdio(false);
  24.     int p, t;
  25.     while (cin >> p >> t, p || t)
  26.     {
  27.         cin.ignore();
  28.         unordered_map<string, int> M;
  29.         for (int i = 0; i < p; ++i)
  30.         {
  31.             string s;
  32.             getline(cin, s);
  33.             M[s] = i;
  34.         }
  35.         vvi G(p), H(p);
  36.         for (int i = 0; i < t; ++i)
  37.         {
  38.             string s, t;
  39.             getline(cin, s);
  40.             getline(cin, t);
  41.             assert(M.find(s) != M.end());
  42.             assert(M.find(t) != M.end());
  43.             int x = M[s], y = M[t];
  44.             G[x].push_back(y);
  45.             H[y].push_back(x);
  46.         }
  47.         vi N(p, -1);
  48.         for (int i = 0; i < p; ++i)
  49.             if (N[i] == -1)
  50.                 scc(G, N, i);
  51.         int num = 0;
  52.         N.assign(p, -1);
  53.         while (!S.empty())
  54.         {
  55.             int k = S.top(); S.pop();
  56.             if (N[k] == -1)
  57.             {
  58.                 num++;
  59.                 scc(H, N, k);
  60.             }
  61.         }
  62.         cout << num << '\n';
  63.     }
  64. }
RAW Paste Data
Want to get better at C++?
Learn to code C++ in 2017
Pastebin PRO Summer Special!
Get 40% OFF on Pastebin PRO accounts!
Top