読者です 読者をやめる 読者になる 読者になる

AOJ 2235

Graph Construction。かなり一般化された問題。平方分割とUnionFindまでは自明に思い浮かぶとして、実装も軽いので投げれば通る。ちなみにUnionFindのオーダーはランクのほうをつかってO(log n)にしないといけないと思います。経路圧縮をするともとに戻せなくなる。

Scootalooとsqrtって似てると思います。

#include<stdio.h>
#include<algorithm>
#include<set>
using namespace std;
int UF[40000];
int BF[40000];
int SCOOT=200;
int chg[400000];
int siz;
int FIND(int a){
	if(UF[a]<0)return a;
	return FIND(UF[a]);
}
void UNION(int a,int b){
	a=FIND(a);
	b=FIND(b);
	if(a==b)return;
	if(UF[a]>UF[b])swap(a,b);
	chg[siz++]=a;
	chg[siz++]=b;
	UF[a]+=UF[b];
	UF[b]=a;
}
int x[40000];
int y[40000];
int z[40000];
set<pair<int,int> >S;
set<pair<int,int> >T;
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		scanf("%d%d%d",x+i,y+i,z+i);
	}
	for(int i=0;i<a;i++)UF[i]=BF[i]=-1;
	for(int i=0;i<b;i++){
		if(i%SCOOT==0){
			T.clear();
			for(int j=0;j<SCOOT&&i+j<b;j++){
				if(x[i+j]!=3){
					T.insert(make_pair(y[i+j],z[i+j]));
					if(x[i+j]==1)S.insert(make_pair(y[i+j],z[i+j]));
					if(x[i+j]==2)S.erase(make_pair(y[i+j],z[i+j]));
				}
			}
			for(int j=0;j<a;j++)UF[j]=BF[j]=-1;
			siz=0;
			set<pair<int,int> >::iterator it=S.begin();
			while(it!=S.end()){
				pair<int,int>W=*it;
	//			if(i==9000){
	//				printf("%d %d\n",W.first,W.second);
	//				fflush(stdout);
	//			}
				if(!T.count(W))UNION(W.first,W.second);
				it++;
			}
			for(int j=0;j<a;j++)BF[j]=UF[j];
		}
		if(x[i]==3){
			set<pair<int,int> >U;
			int n=i/SCOOT*SCOOT;
			for(int j=0;j<i%SCOOT;j++){
				if(x[n+j]==1)U.insert(make_pair(y[n+j],z[n+j]));
				if(x[n+j]==2)U.erase(make_pair(y[n+j],z[n+j]));
			}
			for(int j=min(SCOOT-1,b-n-1);j>i%SCOOT;j--){
				if(x[n+j]==2)U.insert(make_pair(y[n+j],z[n+j]));
				if(x[n+j]==1)U.erase(make_pair(y[n+j],z[n+j]));
			}
			set<pair<int,int> >::iterator it=U.begin();
			siz=0;
			while(it!=U.end()){
				pair<int,int>W=*it;
				UNION(W.first,W.second);
				it++;
			}
			if(FIND(y[i])==FIND(z[i]))printf("YES\n");
			else printf("NO\n");
			for(int j=0;j<siz;j++)UF[chg[j]]=BF[chg[j]];
		}
	}
}

難易度表の750初ACだけど、まあこれはJOIer向けなので…