Advertisement
Guest User

Untitled

a guest
Dec 3rd, 2016
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.92 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <limits>
  5. #include <algorithm>
  6. #include <cassert>
  7.  
  8. using namespace std;
  9.  
  10. // #define DBG
  11.  
  12. enum Query {
  13.     CUT = 0,
  14.     ASK = 1,
  15. };
  16.  
  17. unsigned getRoot(vector<unsigned>& components, unsigned u) {
  18.     unsigned pu = u;
  19.     while (u != components[u]) {
  20.         components[pu] = components[u];
  21.         pu = u;
  22.         u = components[pu];
  23.     }
  24.     return u;
  25. }
  26.  
  27. void connect(vector<unsigned>& components, pair<unsigned, unsigned>& p) {
  28.     unsigned rv = getRoot(components, p.first);
  29.     unsigned ru = getRoot(components, p.second);
  30.     if (rv != ru) components[rv] = ru;
  31. }
  32.  
  33. bool connected(vector<unsigned>& components, pair<unsigned, unsigned>& p) {
  34.     unsigned rv = getRoot(components, p.first);
  35.     unsigned ru = getRoot(components, p.second);
  36.     return (rv == ru)? true : false;
  37. }
  38.  
  39. int main(int argc, char** argv) {
  40.     ios_base::sync_with_stdio(false);
  41.     cout.tie(nullptr);
  42.     unsigned n, m, k;
  43.     cin >> n >> m >> k;
  44.     unsigned a, b; // we do not need the graph
  45.     for (unsigned i = 0; i < m; ++i) { 
  46.         cin >> a >> b;
  47.     }
  48.  
  49.     vector<pair<Query, pair<unsigned, unsigned>>> queries;
  50.     queries.reserve(k);
  51.     string q;
  52.     for (unsigned i = 0; i < k; ++i) {
  53.         cin >> q >> a >> b;
  54.         if (q[0] == 'a') {
  55.             queries.push_back({ASK, {a, b}});
  56.         } else if (q[0] == 'c') {
  57.             queries.push_back({CUT, {a, b}});
  58.         } else assert(false);
  59.     }
  60.  
  61.     vector<unsigned> components(n + 1);
  62.     iota(components.begin(), components.end(), 0);
  63.     vector<bool> ans; ans.reserve(k - m);
  64.     for (auto it = queries.rbegin(); it != queries.rend(); ++it) {
  65.         switch (it->first) {
  66.         case ASK: ans.push_back(connected(components, it->second)); break;
  67.         case CUT: connect(components, it->second); break;
  68.         }
  69. #ifdef DBG
  70.         for (auto && el : components) cout << el << ' '; cout << endl;
  71. #endif
  72.     }
  73.  
  74.     for (auto it = ans.rbegin(); it != ans.rend(); ++it) {
  75.         if (*it) cout << "YES" << endl;
  76.         else cout << "NO" << endl;
  77.     }
  78.  
  79.     return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement