Submission #101816

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)

using namespace std;
typedef long long ll;

const int    INF = 1000000000;
const int    MOD = 1000000007;
const double EPS = 1e-8;
typedef pair<int, int> P;
struct UnionFind{
    vector<int> data;
    UnionFind(int N) : data(N, -1){}
    int root(int x){
        if(data[x] < 0) return x;
        return data[x] = root(data[x]);
    }
    bool uni(int x, int y){
        x = root(x);
        y = root(y);
        if(x == y) return false;
        if(data[x] < data[y]) swap(x, y);
        data[x] += data[y];
        data[y] = x;
        return true;
    }
    bool same(int x, int y){
        return root(x) == root(y);
    }
};

int main(){
    int N, M, K;
    while(cin >> N >> M >> K){
        vector<P> es(M);
        vector<bool> erased(M, false);
        REP(i, M){
            cin >> es[i].first >> es[i].second;
        }
        vector<int> q(K);
        vector<int> v(K), w(K);
        REP(i, K){
            cin >> q[i];
            if(q[i] == 0){
                cin >> v[i];
                erased[ v[i] - 1 ] = true;
            }else{
                cin >> v[i] >> w[i];
            }
        }
        UnionFind uf(N);
        for(int i = 0; i < M; i++) if(not erased[i]) uf.uni(es[i].first - 1, es[i].second - 1);
        vector<int> res;
        for(int i = K - 1; i >= 0; i--){
            if(q[i] == 0){
                int e = v[i] - 1;
                uf.uni(es[e].first - 1, es[e].second - 1);
            }else{
                res.push_back( uf.same(v[i] - 1, w[i] - 1) );
            }
        }
        reverse(res.begin(), res.end());
        for(auto ri : res){
            puts( (ri == 0 ? "NO" : "YES") );
        }
    }
    return 0;
}

Submission Info

Judge Result