yukicoder : No.2319 Friends+

その方法もあったか。
https://yukicoder.me/problems/no/2319

問題

N個のワールドがあり、N人がそれぞれそのいずれかにいる。
友人関係にある2人組の情報がM個与えられる。

以下のクエリが与えられるので、成否をその都度答えよ。

• 2人X,Yが指定される。Yのいるワールドに、Xと友人関係にある人が1人でもいるなら、XはYのいるワールドに移動する。

解法

Xの友人が多い場合と少ない場合で分けて考える。
友人が少ない場合、友人を総当たりしてYと同じワールドにいる人がいるかカウントすればよい。

Xの友人が多い場合、反対に各ワールドにXの友人が何人いるかを覚えさせ、人の移動に合わせて情報を更新しよう。
友人が多い人がO(√N)以下になるように調整すれば、人の移動がO(√N*logN)程度で処理できるようになる。

int N,M,X,Y,Q;
int P[202020];
vector<int> E[20200];
vector<int> B[20200];
map<int,int> num[20202];
const int DI=2000;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>x;
		P[i+1]=x;
	}
	FOR(i,M) {
		cin>>x>>y;
		E[x].push_back(y);
		E[y].push_back(x);
	}
	for(i=1;i<=N;i++) {
		FORR(e,E[i]) {
			if(E[e].size()>=DI) {
				B[i].push_back(e);
				num[P[i]][e]++;
			}
		}
	}
	cin>>Q;
	while(Q--) {
		cin>>X>>Y;
		if(P[X]==P[Y]) {
			cout<<"No"<<endl;
			continue;
		}
		int ok=0;
		if(E[X].size()>=DI) {
			if(num[P[Y]][X]>0) ok=1;
		}
		else {
			FORR(e,E[X]) if(P[e]==P[Y]) ok=1;
		}
		
		if(ok==0) {
			cout<<"No"<<endl;
		}
		else {
			cout<<"Yes"<<endl;
			FORR(e,B[X]) num[P[X]][e]--;
			P[X]=P[Y];
			FORR(e,B[X]) num[P[X]][e]++;
		}
		
	}
}

まとめ

bitsetでも良かったのか…。