クエリの指示に従って、各時点におけるグラフ \(G\) の状態、すなわち各頂点がどの頂点に繋がっているか、および各駒がどの頂点に置かれているかを管理・更新することを考えます。

まず、縮約を行うかどうかの判定について考えます。縮約操作の性質より、\(G_0\) における辺で結ばれている頂点 \(u,v\) について、\(G\) に対してどの縮約が繰り返されても、駒 \(u\) と 駒\(v\) の置かれた頂点は同一でない限りつねに辺で結ばれています。よって、駒 \(u\) の置かれた頂点と駒 \(v\) が置かれた頂点が同一であるかのみ判定できれば良く、各駒がどの頂点に置かれているかの情報から判定を行うことができます。

次に、縮約操作における更新を行う方法について考えます。新しい頂点を作る、あるいは、縮約を行う際、縮約される辺の端点のうち任意に選択した方の頂点を新たな頂点として扱う、という事を行うと、最悪ケースで \(1\) クエリあたり \(O(N+M)\) の時間がかかり、全体で \(O(Q(N+M))\) となるため、実行時間制限に間に合いません。よって、より高速に更新を行う必要があります。ここで、縮約を行う際に、辺の端点のうちどちらを新たな頂点として扱うかという選択を工夫することによって、（マージテクとよばれる技法を用いて）高速に処理する事を考えます。

まず、縮約を行う際に、更新にかかる時間計算量について考えます。縮約する辺の端点を \(u,v\) とし、\(u,v\) にある駒の数をそれぞれ \(P_u, P_v\), 伸びている辺の本数をそれぞれ \(Q_u, Q_v\) とします。ここでは、\(u\) を縮約後の頂点として扱う事を考えます。必要な作業は次のとおりです。

• \(v\) に置かれている駒をすべて \(u\) に動かす。
• \(v\) と辺で繋がっている \(u\) 以外の各頂点 \(x\) について、\(x\) と \(u\) が繋がっていないならば、\(x\) と \(u\) を新たに辺でつなぐ。
• \(v\) と他の頂点を結ぶ辺を削除する。
• \(v\) を削除する。

\(1\) つめの作業については、\(O(P_v)\) で行うことができます。
\(2\) つめの作業については、愚直に行うと、\(O(Q_uQ_v)\) かかりますが、各頂点の隣接リストを適切なデータ構造 (std::set 等)で管理することで、\(O(Q_v\log Q_u)\) 、特に高々 \(O(Q_v\log N)\) で行うことができます。
\(3\) つめの作業については、隣接リストを std::set 等で管理している場合、\(O(Q_v\log N)\) かかります。
\(4\) つめの作業については定数時間で行うことができます。
よって、合計で高々 \(O(P_v+Q_v\log N)\) , 特に \(O((P_v+Q_v)\log N)\) の計算量で行うことができます。

ここで、各縮約において、\((P_u+Q_u)\geq (P_v+Q_v)\) のときかつその時に限り、\(u\) を縮約後の頂点として選択すると定めると、一連の縮約操作全体で、縮約の手順にかかる時間計算量が \(O((N+M)\log (N+M)\log N)\) で抑えられる事が証明できます。 縮約は行うたびに頂点数が \(1\) 減少するため、クエリの回数によらず、高々 \(N-1\) 回しか行われないことに注意してください。

なお、\(G\) 全体の辺の本数管理は上記で辺の追加・削除の操作を行うたびに \(1\) 増減させれば良いため、高々 \(O(M\log(N+M))\) で行うことができます。（実際は追加操作はかならず他方の頂点から伸びる辺の削除操作と相殺するため、追加操作を反映する必要がないように更新を行うことができ、\(O(M)\) で行うことができます。）

さて、全体で問題を解くのにかかる計算量について考えます。駒および辺の初期状態を設定するのにかかる時間計算量は \(O(N+M\log N)\) です。各クエリについて縮約操作を行うかの判定は \(O(1)\) で行うことができます。縮約によるグラフの更新操作は全体で \(O((N+M)\log(N+M)\log N )\) で行うことができることから、全体で \(O(Q+(N+M)\log(N+M)\log N)\) この問題を解くことができ、これは今回の問題の制約下で十分高速です。 よって、この問題を解くことができました。

c++ による実装例:

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

#define N (int)3e+5

int main() {
	int n,m;
	int u[N],v[N];
	vector<int>p[N];
	int p_rev[N];
	set<int> e[N];
	
	cin>>n>>m;
	for(int i=0;i<n;i++){
		p_rev[i]=i;
		p[i].push_back(i);
	}
	for(int i=0;i<m;i++){
		cin>>u[i]>>v[i];
		u[i]--;v[i]--;
		e[u[i]].insert(v[i]);
		e[v[i]].insert(u[i]);
	}

	int q,x;
	cin>>q;
	for(int i=0;i<q;i++){
		cin>>x;
		int vx=p_rev[u[x-1]];
		int vy=p_rev[v[x-1]];
		if(vx!=vy){
		  	int valx=(e[vx].size())+(p[vx].size());
			int valy=(e[vy].size())+(p[vy].size());
			if(valx>valy)swap(vx,vy);

			int sz=p[vx].size();
			for(int j=0;j<sz;j++){
				p[vy].push_back(p[vx][j]);
				p_rev[p[vx][j]]=vy;
			}
			p[vx].clear();

			set<int>::iterator itr=e[vx].begin();
			while(itr!=e[vx].end()){
				int vz=(*itr);
				if(vz==vy){
					m--;
					e[vy].erase(vx);
				}
				else{
					if(e[vy].count(vz)==1)m--;
					else{
						e[vy].insert(vz);
						e[vz].insert(vy);
					}
					e[vz].erase(vx);
				}
				itr++;
			}
			e[vx].clear();
		}
		cout<<m<<endl;
	}
	return 0;
}