AT_abc302_e

题意

给定一个有 \(n\) 个点的无向图。初始没有任何边。

接下来有 \(q\) 次操作，分为 \(2\) 种类型：

• 1 u v：连接 \(u\) 和 \(v\),保证没有重边、自环。

• 2 v：删除连接 \(v\) 的所有边。

每次操作后，输出没有连接其它任何点的点的数量（即度数为 \(0\) 的点的数量）。

思路

看到操作次数 \(1 \le q \le 3 \times 10^5\)，可以推测输出的答案需要动态维护。而看到边可加可删，推测每次操作可以直接暴力加边、删边，一旦点的度数由 \(0\) 变 \(1\) 或由 \(1\) 变 \(0\) 时，则更新答案。

详细操作见代码：

#include <iostream>
#include <cstdio>
#include <set>

using namespace std;

set<int> G[1000001];
int n,m,t,x,y,ans,len;

int main()
{
	cin >> n >> m;
	ans = n;
	for( int i = 1 ; i <= m ; i ++ )
	{
		cin >> t;
		if( t == 1 )
		{
			cin >> x >> y;
			if( !G[x].size() ) ans --;
			if( !G[y].size() ) ans --;
			G[x].insert( y );
			G[y].insert( x );
		}
		if( t == 2 )
		{
			cin >> x;
			if( G[x].size() ) ans ++;
			for( auto j : G[x])
			{
				G[j].erase(x);
				if( !G[j].size() ) ans ++;
			}
			G[x].clear();
		}
		cout << ans << endl;
	}
	return 0;
}