Submission #101936

---

Source Code Expand

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

using namespace std;

typedef pair<int,int> P;

const int MAX = 1e5+1;

struct query{int q, a,b;};
class UnionFind{
public:
	vector<int> par;
	vector<int> rank;
	void init(int n){
		par.resize(n);
		rank.resize(n);

		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 N,M,K;

int main(){

	UnionFind uf;
	cin >> N >> M >> K;
	uf.init(N);
	
	vector<P> E;
	for(int i = 0; i < M; i++){
		P p;
		cin >> p.first >> p.second;
		p.first--;
		p.second--;
		E.push_back(p);
	}
	
	vector<query> Q(K);
	for(int i = 0; i < K; i++){
		cin >> Q[i].q;
		if(Q[i].q == 0) cin >> Q[i].a;
		else cin >> Q[i].a >> Q[i].b;
		Q[i].a--;
		Q[i].b--;
	}

	reverse(Q.begin(),Q.end());
	vector<bool> ans;

	bool erase[MAX];
	memset(erase,false,sizeof(erase));

	for(int i = 0; i < (int)Q.size();i++){
		if(Q[i].q == 0) erase[Q[i].a] = true;
	}

	for(int i = 0; i < E.size(); i++)
		if(!erase[i]) uf.unite(E[i].first,E[i].second);

	
	for(int i = 0; i < Q.size(); i++){
		if(Q[i].q == 0) uf.unite(E[Q[i].a].first,E[Q[i].a].second);
		else ans.push_back(uf.same(Q[i].a, Q[i].b));
	}
	reverse(ans.begin(),ans.end());

	for(int i = 0; i < ans.size(); i++)
		if(ans[i]) cout << "YES" << endl;
		else cout << "NO" << endl;
								 
	return 0;
}

Submission Info

Judge Result