Solution 1: managing edges with an ordered set (\(O(Q\log N)\) solution)

Consider managing, for each vertex, the set of vertices that are adjacent to that vertex. If we denote the vertex set adjacent to vertex \(v\) by \(S_u\), then
the query of the first kind asks:

• to add \(v\) to \(S_u\) and \(u\) to \(S_v\).

The query of the second kind asks:

• to remove \(v\) from \(S_u\) for each \(u\in S_v\); and
• to empty \(S_v\).

The query of the second type performs \(\lvert S_v\rvert\) removals; however, note that all the edges to be removed are those added by the query of the first kind in prior, so at most \(Q\) removals are required at most in total.

If you naively manage the vertices with a vector, addition can be performed in an \(O(1)\) time, while removing an element from a vector requires at worst \(\Theta(\mathrm{length})\) time. Since the length of the vector can be up to \(N\), the complexity may reach \(\Theta(NQ))\) time, which does not fit in the time limit.

Instead, if we manage the vertices with a set, a removal of an element requires an \(O(\log N)\), so it can be done in a total of \(O(Q\log N)\) time. All that left is to monitor if an addition or removal of an edge changes the number of “the vertices that are not connected to any other vertices by an edge,” i.e. the number of vertices \(v\) such that \(\lvert S_v\rvert=0\). Therefore, the problem has been solved.

2: managing whether an edge is removed separately (\(O(Q)\) solution)

We used to manage the sets of adjacent vertices for each vertex. But instead we may, for each vertex \(v\), for each edge adjacent to \(v\) added after the last query of the second kind applied to \(v\), record the new adjacent vertex connected by the edge and the index of query that added the edge; we also manage separately whether each edge added by query of the first kind was removed or not. In this case, the vertices connected to \(v\) are “the adjacent vertices connected by edges added after the last query of the second kind applied to \(b\)” such that the edges connecting the adjacent vertices are not removed yet. Also, in this case, the number of vertices adjacent to \(v\) is not represented by the size of sets, so it should also be managed separately. By recording whether it was removed or not, we avoid removing edges from both ends twice.

This way, an additions and removal of an edge can be done in an \(O(1)\) time, for a total of \(O(Q)\) time.

Sample code in C++ (Solution 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;
}

Sample code in C++ (solution 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;
}