解法1: 辺の情報を順序付き集合で管理する解法（ \(O(Q\log N)\) 解法 ）

各頂点についてその頂点と辺で繋がっている頂点集合を管理する事を考えます。頂点 \(v\) と辺で繋がっている頂点の集合を \(S_u\) とする時、
\(1\) 番目のタイプのクエリでは、

• \(S_u\) に \(v\) を追加し、\(S_v\) に \(u\) を追加する。

\(2\) 番目のタイプのクエリでは、

• 各 \(u\in S_v\) について、\(S_u\) から \(v\) を取り除く。
• \(S_v\) を空にする。

という操作を行う必要があります。ここで、 \(2\) 番目のタイプのクエリにおいて \(\lvert S_v\rvert\) 回 削除操作を行なっていますが、削除される辺は \(1\) 番目のタイプのクエリによって追加されたものしかあり得ないため、全てのクエリを通じて高々 \(Q\) 回しか行われない事に注意します。

もし、vectorを用いて愚直に管理したとすると、要素の追加は \(O(1)\) で行えるため問題ありませんが、vectorから特定の要素を削除するには、最悪 \(\Theta(\mathrm{長さ})\) の計算量がかかるため、vectorの長さが最大で \(N\) となる事に注意すると、 \(\Theta(NQ))\) の計算回数が必要になる可能性があり、間に合いません。

そこで、setを用いて管理する事によって、要素の追加も削除も \(O(\log N)\) で行う事ができ、全体で \(O(Q\log N)\) の計算量で管理する事ができます。 あとは、辺を追加・削除するタイミングで「どの他の頂点とも繋がっていない頂点」の数、すなわち \(\lvert S_v\rvert=0\) であるような頂点 \(v\) の数が変化したかをシミュレーションしていけば答えは求まります。よって、この問題を解く事ができました。

2. 辺が削除済みであるかどうかを別に管理する方法 （\(O(Q)\) 解法）

各頂点について、その頂点と辺で繋がっている頂点集合を管理する代わりに、各頂点 \(v\) について、最後に \(v\) に対して \(2\) 番目のタイプのクエリが行われてから \(v\) と結ばれた頂点の、頂点番号と何個目のクエリで繋げられたかを記録し、それとは別にそれぞれのタイプ \(1\) のクエリで繋げられた辺が削除されたかを管理するという方法もあります。この場合、\(v\) と繋がっている頂点は、「最後に \(v\) に対して \(2\) 番目のタイプのクエリが行われてから \(v\) と結ばれた頂点」のうち \(v\) とその頂点を結んだ辺がまだ削除されていないものとなります。また、この場合、\(v\) と繋がっている頂点の数は集合のサイズなどでは表されないため、別途管理する必要があります。削除されたかを記録しておく事で、両端の頂点から二重に削除されてしまう事を防いでいます。

このとき辺の追加・削除を \(O(1)\) で行う事ができ、計算量は全体で \(O(Q)\) となります。

c++による実装例(解法1):

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

#define rep(i, n) for(int i = 0; i < n; ++i)

int main(void) {
	int n,q,t,x,y,ans;
	cin>>n>>q;
	vector<set<int>>e(n);
	set<int>::iterator itr;
	ans=n;
	rep(i,q){
		cin>>t;
		if(t==1){
			cin>>x>>y;
			x--,y--;
			if(e[x].size()==0)ans--;
			if(e[y].size()==0)ans--;
			e[x].insert(y);
			e[y].insert(x);
		}
		else{
			cin>>x;
			x--;
			itr=e[x].begin();
			while(itr!=e[x].end()){
				y=*itr;
				e[y].erase(x);
				if(e[y].size()==0)ans++;
				itr++;
			}
			if(e[x].size()>0)ans++;
			e[x].clear();
		}
		cout<<ans<<endl;
	}
	return 0;
}

c++による実装例(解法2):

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

#define rep(i, n) for(int i = 0; i < n; ++i)


int main(void) {
	int n,q,t,x,y,sz,ans;
	cin>>n>>q;
	vector<int>c(n);
	vector<bool>ex(q,true);
	vector<vector<pair<int,int> > >e(n);
	ans=n;
	rep(i,q){
		cin>>t;
		if(t==1){
			cin>>x>>y;
			x--,y--;
			if(c[x]==0)ans--;
			if(c[y]==0)ans--;
			c[x]++;
			c[y]++;
			e[x].push_back({y,i});
			e[y].push_back({x,i});
		}
		else{
			cin>>x;
			x--;
			sz=e[x].size();
			rep(j,sz){
				if(ex[e[x][j].second]){
					ex[e[x][j].second]=false;
					c[e[x][j].first]--;
					if(c[e[x][j].first]==0)ans++;
				}
			}
			e[x].clear();
			if(c[x]>0)ans++;
			c[x]=0;
		}
		cout<<ans<<endl;
	}
	return 0;
}