[bzoj3562]-[SHOI2014]神奇化合物

题目（BZOJ）
做题先看数据范围：q远小于m。
说明啥？说明很多条边都没有被操作。
所以，将没有操作过的边上的点放到一个集合里面去，这就是用并查集缩点。
删边和加边的话，直接暴力跑过去就行。
完毕。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
template <class ___E> inline void read(___E &e)
{
	e=0;bool ck=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')ck=1;ch=getchar();}
	while(ch>='0'&&ch<='9'){e=e*10+ch-'0';ch=getchar();}
	if(ck) e = -e;
}
int f[5005];
int find(int x)
{
	return x==f[x]?x:f[x]=find(f[x]);
}
int n,m,q;
int Q;
int qiao[5005][5005];
struct edge{
	int vk;
	int nxt;
}e[500005];
int t,head[5005];
void ad(int u,int v)
{
	e[++t].vk=v;
	qiao[u][v]++;
	e[t].nxt=head[u];
	head[u]=t;
}
struct query{
	int x,y;
	int col;
}a[10005];
bool d[5005][5005];
bool vis[5005];
int x[200005],y[200005];
int cnt;
bool dfs(int xx,int yy)
{
	if (xx==yy) return true;
	for (int i=head[xx];i;i=e[i].nxt)
	{
		int v=e[i].vk;
		if (qiao[xx][v]>0 && !vis[v])
		{
			vis[v]=1;
			if (dfs(v,yy)) return true;
		}
	}
	return false;
}
inline void del(int xx,int yy)
{
	qiao[xx][yy]--,qiao[yy][xx]--;
	memset(vis,0,sizeof vis);
	if (!dfs(xx,yy)) cnt++;
}
int main()
{
	read(n),read(m);
	for (int i=1;i<=n;++i) f[i]=i;
	for (int i=1;i<=m;++i)
		read(x[i]),read(y[i]);
	read(q);
	while (q--)
	{
		char s;
		int x,y;
		cin>>s;
		if (s=='Q')
			a[++Q].col=1;
		else
		{
			read(x),read(y);
			a[++Q].x=x,a[Q].y=y;
			if (s=='A') a[Q].col=2;
			else if (s=='D') a[Q].col=3,d[x][y]=d[y][x]=1;
		}
	}
	for (int i=1;i<=m;++i)
	{
		if (!d[x[i]][y[i]])
		{
			int px=find(x[i]);
			int py=find(y[i]);
			if (px!=py) f[px]=py;
		}
	}
	for (int i=1;i<=n;++i)
	{
		int p=find(i);
		f[i]=p;
		if (f[i]==i) ++cnt;
	}
	for (int i=1;i<=m;++i)
	{
		if (f[x[i]]!=f[y[i]])
		{
			memset(vis,0,sizeof vis);
			if (!dfs(f[x[i]],f[y[i]])) cnt--;
			ad(f[x[i]],f[y[i]]),
			ad(f[y[i]],f[x[i]]);
		}
	}
	for (int i=1;i<=Q;++i)
	{
		if (a[i].col==1) printf("%d\n",cnt);
		else if (a[i].col==2)
		{
			memset(vis,0,sizeof vis);
			if (!dfs(f[a[i].x],f[a[i].y])) cnt--;
			ad(f[a[i].x],f[a[i].y]),ad(f[a[i].y],f[a[i].x]);
		}
		else del(f[a[i].x],f[a[i].y]);
	}
	return 0;
}