Submission #101921

---

Source Code Expand

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

int N,E,K;

const int MAX_N = 100000;

int par[MAX_N];
int rank[MAX_N];

typedef pair<int,int>P;

struct Edge{
  int from,to;
  bool used;
};

void init(){
  for(int i = 0 ; i < N ; i++){
    par[i] = i;
    rank[i] = 0;
  }
}

int find(int x){
  if(par[x] == x){
    return x;
  }else {
    return par[x] = find(par[x]);
  }
}

void unite(int x,int y){
  x = find(x);
  y = find(y);
  if(x == y)return;

  if(rank[x] < rank[y]){
    par[x] = y;
  }
  else {
    par[y] = x;
    if(rank[x] == rank[y])rank[x]++;
  }
}

bool same(int x,int y){
  return find(x) == find(y);
}

int main(){
  cin >> N >> E >> K;
  vector<Edge>edges;
  for(int i = 0 ; i < E ; i++){
    Edge e; cin >> e.from >> e.to;
    e.from--;
    e.to--;
    e.used = false;
    edges.push_back(e);
  }

  vector<P>vec;
  for(int i = 0 ; i < K ; i++){
    P p;
    int a;
    cin >> a;
    if(a){
      cin >> p.first >> p.second;
      p.first--;
      p.second--;
    }
    else {
      cin >> p.first;
      p.first--;
      edges[p.first].used = true;
      p.second = -1;
    }
    vec.push_back(p);
  }

  init();
  for(int i = 0 ; i < E ; i++){
    if(!edges[i].used){
      //cout << edges[i].from+1 << ' ' << edges[i].to+1  << endl;
      unite(edges[i].from,edges[i].to);
    }
  }
  /*
  for(int i = 0 ; i < N ; i++){
    cout << "i = " << i+1 << " find : " << find(i) << endl;
  }
  */

  vector<int>res;
  for(int i = K-1 ; i >= 0 ; i--){
    if(vec[i].second == -1){
      int id = vec[i].first;
      unite(edges[id].from,edges[id].to);
    }
    else {
      res.push_back(same(vec[i].first,vec[i].second));
      /*
      cout << vec[i].first+1 << ' ' << vec[i].second+1 << endl;//
      cout << find(vec[i].first)+1 << ' ' << find(vec[i].second)+1 << endl;//
      cout << same(vec[i].first,vec[i].second) << endl;
      cout << endl;
      */
    }
  }
  
  reverse(res.begin(),res.end());
  for(int i = 0 ; i < res.size() ; i++){
    cout << (res[i]?"YES":"NO") << endl;
  }

  return 0;
}

Submission Info

Judge Result