Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cmath>
- #include <limits>
- #include <algorithm>
- #include <cassert>
- using namespace std;
- // #define DBG
- enum Query {
- CUT = 0,
- ASK = 1,
- };
- unsigned getRoot(vector<unsigned>& components, unsigned u) {
- unsigned pu = u;
- while (u != components[u]) {
- components[pu] = components[u];
- pu = u;
- u = components[pu];
- }
- return u;
- }
- void connect(vector<unsigned>& components, pair<unsigned, unsigned>& p) {
- unsigned rv = getRoot(components, p.first);
- unsigned ru = getRoot(components, p.second);
- if (rv != ru) components[rv] = ru;
- }
- bool connected(vector<unsigned>& components, pair<unsigned, unsigned>& p) {
- unsigned rv = getRoot(components, p.first);
- unsigned ru = getRoot(components, p.second);
- return (rv == ru)? true : false;
- }
- int main(int argc, char** argv) {
- ios_base::sync_with_stdio(false);
- cout.tie(nullptr);
- unsigned n, m, k;
- cin >> n >> m >> k;
- unsigned a, b; // we do not need the graph
- for (unsigned i = 0; i < m; ++i) {
- cin >> a >> b;
- }
- vector<pair<Query, pair<unsigned, unsigned>>> queries;
- queries.reserve(k);
- string q;
- for (unsigned i = 0; i < k; ++i) {
- cin >> q >> a >> b;
- if (q[0] == 'a') {
- queries.push_back({ASK, {a, b}});
- } else if (q[0] == 'c') {
- queries.push_back({CUT, {a, b}});
- } else assert(false);
- }
- vector<unsigned> components(n + 1);
- iota(components.begin(), components.end(), 0);
- vector<bool> ans; ans.reserve(k - m);
- for (auto it = queries.rbegin(); it != queries.rend(); ++it) {
- switch (it->first) {
- case ASK: ans.push_back(connected(components, it->second)); break;
- case CUT: connect(components, it->second); break;
- }
- #ifdef DBG
- for (auto && el : components) cout << el << ' '; cout << endl;
- #endif
- }
- for (auto it = ans.rbegin(); it != ans.rend(); ++it) {
- if (*it) cout << "YES" << endl;
- else cout << "NO" << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement