Raslboyy

2786

Nov 24th, 2019
195
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.34 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <list>
  4. #include <algorithm>
  5. #include <string>
  6. #include <math.h>
  7. #include <climits>
  8. #include <stack>
  9.  
  10. //#include <chrono>
  11. //#include <fstream>
  12. //#include <bits/stdc++.h>
  13.  
  14. #define mp make_pair
  15. #define pb push_back
  16. #define eb emplace_back
  17. #define x first
  18. #define y second
  19. #define sz(x) (int)x.size()
  20. #define all(x) begin(x), end(x)
  21. #define rall(x) rbegin(x), rend(x)
  22. #define FOR(i,a,b) for (int i = (a); i < (b); i++)
  23. #define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
  24.  
  25. using namespace std;
  26.  
  27. typedef unsigned long long ull;
  28. typedef long long ll;
  29. typedef long double ld;
  30. typedef pair<int, int> pi;
  31. typedef pair<ll, ll> pl;
  32. typedef vector<int> veci;
  33. typedef vector<bool> vecb;
  34. typedef vector<vector<int>> vvi;
  35. typedef vector<vector<bool>> vvb;
  36.  
  37. const int INF_I = 1e9;
  38. const ll INF_LL = 1e18;
  39.  
  40. class DSU {
  41. public:
  42.     DSU(int n) {
  43.         this->n = n;
  44.         p.assign(n, 0);
  45.         sz.assign(n, 0);
  46.         for (int i = 0; i < n; i++)
  47.             p[i] = i;
  48.     }
  49.  
  50.     void union_sets(int a, int b) {
  51.         a = find_set(a);
  52.         b = find_set(b);
  53.         if (a != b) {
  54.             if (sz[a] < sz[b])
  55.                 swap(a, b);
  56.             p[b] = a;
  57.             sz[a] += sz[b];
  58.         }
  59.     }
  60.  
  61.     bool get(int a, int b) {
  62.         return find_set(a) == find_set(b);
  63.     }
  64.  
  65. private:
  66.     int n;
  67.     veci p;
  68.     veci sz;
  69.  
  70.     int find_set(int v) {
  71.         return (v == p[v] ? v : p[v] = find_set(p[v]));
  72.     }
  73. };
  74.  
  75. int main() {
  76.     /*ifstream cin("in.txt");
  77.     ofstream cout("out.txt");
  78.     auto start_time = chrono::high_resolution_clock::now();*/
  79.  
  80.     ios::sync_with_stdio(false);
  81.     cin.tie(0);
  82.     cout.tie(0);
  83.  
  84.    
  85.     int n, m, k;
  86.     cin >> n >> m >> k;
  87.     for (int i = 0; i < m; i++) {
  88.         int a;
  89.         cin >> a >> a;
  90.     }
  91.  
  92.     stack<pair<bool, pi>> q;
  93.     for (int i = 0; i < k; i++) {
  94.         string str; int a, b;
  95.         cin >> str >> a >> b;
  96.         --a, --b;
  97.         if (str[0] == 'a')
  98.             q.emplace(mp(0, mp(a, b)));
  99.         else
  100.             q.emplace(mp(1, mp(a, b)));
  101.     }
  102.     DSU d(n);
  103.     stack<bool> res;
  104.     while (!q.empty()) {
  105.         pair<int, pi> p = q.top();
  106.         q.pop();
  107.         if (p.x)
  108.             d.union_sets(p.y.x, p.y.y);
  109.         else
  110.             res.emplace(d.get(p.y.x, p.y.y));
  111.     }
  112.     while (!res.empty()) {
  113.         cout << (res.top() ? "YES" : "NO") << "\n";
  114.         res.pop();
  115.     }
  116.  
  117.     /*auto end_time = chrono::high_resolution_clock::now();
  118.     chrono::duration<double> duration = end_time - start_time;
  119.     cout << duration.count() << "\n";
  120.     cin.close();
  121.     cout.close();*/
  122.     return 0;
  123. }
Advertisement
Add Comment
Please, Sign In to add comment