Submission #102478

---

Source Code Expand

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


#define FOR(i, a, n) for(int i = (a); i < (n); i++)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, n) for(int i = (n) - 1; i >= (a); i--)
#define RREP(i, n) RFOR(i, 0, n)
#define fst first
#define snd second

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAX_N = 110000;
const int MAX_M = 110000;
const int MAX_K = 110000;

int n, m, k;
vector<int> g[MAX_N];
pii es[MAX_M];
bool deleted[MAX_N];

int t[MAX_K], a1[MAX_K], a2[MAX_K];

struct UnionFind{
  
  int n;
  vector<int> par, rank;
  

  UnionFind(int n_){
	n = n_;
	par = vector<int>(n);
	rank = vector<int>(n);
	REP(i, n){
	  par[i] = i;
	  rank[i] = 0;
	}
  }
  

  int find(int x){
	return (x == par[x]) ? x : 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);
  }
  
};

vector<bool> solve(){
  vector<bool> r;

  UnionFind uf(n);
  REP(i, m){
	if(!deleted[i]){
	  g[es[i].fst].push_back(es[i].snd);
	  g[es[i].snd].push_back(es[i].fst);
	  uf.unite(es[i].fst, es[i].snd);
	}
  }

  RREP(i, k){
	if(t[i] == 0){
	  k = a1[i];
	  g[es[k].fst].push_back(es[k].snd);
	  g[es[k].snd].push_back(es[k].fst);
	  uf.unite(es[k].fst, es[k].snd);
	}else{
	  r.push_back(uf.same(a1[i], a2[i]));
	}
  }
  
  reverse(r.begin(), r.end());
  return r;
}

int main(){
  cin >> n >> m >> k;
  REP(i, n) g[i].clear();
  REP(i, m){
	cin >> es[i].fst >> es[i].snd;
	es[i].fst--, es[i].snd--;
  }
  REP(i, k){
	cin >> t[i];
	if(t[i] == 0){
	  cin >> a1[i];
	  a1[i]--;
	  deleted[a1[i]] = true;
	}else{
	  cin >> a1[i] >> a2[i];
	  a1[i]--, a2[i]--;
	}
  }
  
  vector<bool> r = solve();
  REP(i, (int)r.size()){
	cout << (r[i] ? "YES" : "NO") << endl;
  }
  return 0;
}

Submission Info

Judge Result