Submission #2044922

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int n,m,k,a[100009],b[100009],c1[100009],c2[100009],c3[100009],ans[100009];bool used[100009];

class UnionFind{
	public:
	vector<int>par;
	void init(int size_){
		par.resize(size_+2,-1);
	}
	int root(int pos){
		if(par[pos]==-1) return pos;
		par[pos]=root(par[pos]);
		return par[pos];
	}
	bool same(int u,int v){
		if(root(u)==root(v)) return true;
		return false;
	}
	void unite(int u,int v){
		u=root(u);v=root(v);
		if(u==v) return;
		par[u]=v;
	}
};

int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++) cin>>a[i]>>b[i];
	for(int i=1;i<=k;i++){
		cin>>c1[i];
		if(c1[i]==1) cin>>c2[i]>>c3[i];
		else{cin>>c2[i];used[c2[i]]=true;}
	}
	UnionFind UF;UF.init(n+2);
	for(int i=1;i<=m;i++){
		if(used[i]==false) {
			UF.unite(a[i],b[i]);
		}
	}
	for(int i=k;i>=1;i--){
		if(c1[i]==1){
			if(UF.same(c2[i],c3[i])==true) ans[i]=1;
		}
		else{
			UF.unite(a[c2[i]],b[c2[i]]);
		}
	}
	for(int i=1;i<=k;i++){
		if(c1[i]==0) continue;
		if(ans[i]==1) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}

Submission Info

Judge Result