Advertisement
radmickey

Untitled

Mar 16th, 2023
531
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.06 KB | None | 0 0
  1. #include <vector>
  2. #include <iostream>
  3. #include <fstream>
  4.  
  5. std::vector <std::vector<int>> g, gr;
  6. std::vector<char> used;
  7. std::vector<int> order, component;
  8.  
  9. void dfs1 (int v) {
  10.     used[v] = true;
  11.     for (size_t i=0; i<g[v].size(); ++i)
  12.         if (!used[ g[v][i] ])
  13.             dfs1 (g[v][i]);
  14.     order.push_back (v);
  15. }
  16.  
  17. void dfs2 (int v) {
  18.     used[v] = true;
  19.     component.push_back (v);
  20.     for (size_t i=0; i<gr[v].size(); ++i)
  21.         if (!used[ gr[v][i] ])
  22.             dfs2 (gr[v][i]);
  23. }
  24.  
  25. int main() {
  26.     for (int ii = 1; ii < 2; ii++) {
  27. //        std::ifstream cin(std::to_string(ii).c_str());
  28.         int n, m, q;
  29.         std::cin >> n >> m >> q;
  30.  
  31.         g.resize(n);
  32.         gr.resize(n);
  33.  
  34.         for (int i = 0; i < m; i++) {
  35.             int a, b;
  36.             std::cin >> a >> b;
  37.             a--;
  38.             b--;
  39.             g[a].push_back(b);
  40.             gr[b].push_back(a);
  41.         }
  42.  
  43.         used.assign(n, false);
  44.         for (int i = 0; i < n; ++i) {
  45.             if (!used[i]) {
  46.                 dfs1(i);
  47.             }
  48.         }
  49.         used.assign(n, false);
  50.  
  51.         std::vector<std::vector<int>> components;
  52.  
  53.         for (int i = 0; i < n; ++i) {
  54.             int v = order[n - 1 - i];
  55.             if (!used[v]) {
  56.                 dfs2(v);
  57.                 components.emplace_back(component);
  58.                 component.clear();
  59.             }
  60.         }
  61.  
  62.         std::vector<int> ver(n, 0);
  63.         for (int i = 0; i < components.size(); i++) {
  64.             for (auto j: components[i]) {
  65.                 ver[j] = i;
  66.             }
  67.         }
  68.  
  69.         std::vector<bool> answer(q);
  70.         for (int j = 0; j < q; j++) {
  71.             int a, b;
  72.             std::cin >> a >> b;
  73.             a--;
  74.             b--;
  75.             answer[j] = (ver[a] == ver[b]);
  76.         }
  77. //        std::ofstream cout((std::to_string(ii) + ".a").c_str());
  78.  
  79.         for (auto j: answer) {
  80.             if (j) {
  81.                 std::cout << "YES\n";
  82.             } else {
  83.                 std::cout << "NO\n";
  84.             }
  85.         }
  86.     }
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement