Submission #101832

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Query {
    int type;
    int e, v, w;
};

int root(int x, vector<int> &roots) {
    if(roots[x] == x) return x;
    return roots[x] = root(roots[x], roots);
}

void unite(int x, int y, vector<int> &roots) {
    x = root(x, roots);
    y = root(y, roots);
    if(x == y) return;
    roots[x] = y;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int N, M, K;
    cin >> N >> M >> K;
    vector<int> roots(N);
    vector<pair<int,int> > edges(M);
    vector<int> remains(M, 1);
    vector<Query> queries(K);
    for(int i = 0; i < N; ++i) {
        roots[i] = i;
    }
    for(int i = 0; i < M; ++i) {
        cin >> edges[i].first >> edges[i].second;
        edges[i].first--;
        edges[i].second--;
    }
    for(int i = 0; i < K; ++i) {
        cin >> queries[i].type;
        if(queries[i].type == 0) {
            cin >> queries[i].e;
            queries[i].e--;
            remains[queries[i].e] = 0;
        } else {
            cin >> queries[i].v >> queries[i].w;
            queries[i].v--;
            queries[i].w--;
        }
    }
    for(int i = 0; i < M; ++i) {
        if(remains[i]) {
            unite(edges[i].first, edges[i].second, roots);
        }
    }
    reverse(queries.begin(), queries.end());
    vector<int> res;
    for(const Query &q : queries) {
        if(q.type == 0) {
            const pair<int,int> &e = edges[q.e];
            unite(e.first, e.second, roots);
        } else {
            if(root(q.v, roots) == root(q.w, roots)) {
                res.push_back(1);
            } else {
                res.push_back(0);
            }
        }
    }
    reverse(res.begin(), res.end());
    for(int n : res) {
        cout << (n ? "YES" : "NO") << endl;
    }
    return 0;
}

Submission Info

Judge Result