これ系のテク自分で使ったの初めてだけど意外にすんなり書けた。
https://code-thanks-festival-2017-open.contest.atcoder.jp/tasks/code_thanks_festival_2017_h
問題
N個の頂点があり、M個の辺を順に追加していくことを考える。
ここでQ個のクエリが与えられる。
各クエリは2頂点対X,Yからなる。
X,Yが連結成分となるのは何本目の辺を追加したときか答えよ。
解法
並列二分探索で解く。
各クエリに対し、解の候補となる区間を初期状態として[1,M+1]と持たせて置く。
今解の候補が[L,R]であるなら、(L+R)/2本辺を追加を追加した時点で連結しているかどうかを持ってL,Rを更新しよう。
一回の探索で範囲を半分に狭められるので、Union-Findを用いてlog(M)回程度M個の辺追加をシミュレートすれば解を特定できる。
int N,M,Q; int A[101010],B[101010]; int X[101010],Y[101010]; int L[101010],R[101010]; vector<int> cand[101010]; template<int um> class UF { public: vector<int> par,rank; UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);} int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));} int operator()(int x,int y) { if((x=operator[](x))==(y=operator[](y))) return x; if(rank[x]>rank[y]) return par[x]=y; rank[x]+=rank[x]==rank[y]; return par[y]=x; } }; UF<500000> uf; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,M) { cin>>A[i]>>B[i]; A[i]--; B[i]--; } cin>>Q; FOR(i,Q) { cin>>X[i]>>Y[i]; X[i]--; Y[i]--; L[i]=1; R[i]=M+1; } FOR(i,20) { FOR(x,Q) cand[(L[x]+R[x])/2].push_back(x); FOR(x,N) uf.par[x]=x, uf.rank[x]=0; FOR(x,M) { uf(A[x],B[x]); FORR(e,cand[x+1]) { if(uf[X[e]]==uf[Y[e]]) { R[e]=x+1; } else { L[e]=x+2; } } cand[x+1].clear(); } } FOR(i,Q) { if(L[i]>M) cout<<-1<<endl; else cout<<L[i]<<endl; } }
まとめ
LCA解は思いつかなかった…。