【传送门：】
简要题意：
给出n个点，m条初始无向边，有3种操作，q个操作：
A x y连接x和y
D x y删除x和y的边
Q 求出有多少个连通块
题解：
并查集+DFS
因为询问很少，但是边很多，所以我们先离线将不会被删除的边拿出来，然后将永远连在一起的点缩点
这样子这个图就会变得很小
然后直接暴搜插边删边，其中维护连通块数就行了
T到发狂。。判断了一下重边就A了
参考代码：
#include#include #include #include #include #include using namespace std;struct node{ int x,y,d,next;}a[510000];int len,last[5100];void ins(int x,int y){ len++; a[len].x=x;a[len].y=y; a[len].next=last[x];last[x]=len;}int fa[5100];int findfa(int x){ if(fa[x]!=x) fa[x]=findfa(fa[x]); return fa[x];}int x[210000],y[210000];struct question{ int opt,x,y;}q[11000];int map[5100][5100];int cnt;int v[5100];bool bk;int belong[5100];void dfs(int x,int ed,int t){ if(x==ed) bk=true; if(bk==true) return ; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(v[y]!=t&&a[k].d>0) { v[y]=t; dfs(y,ed,t); if(bk==true) return ; } }}int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d",&x[i],&y[i]); int Q; scanf("%d",&Q); memset(map,0,sizeof(map)); for(int i=1;i<=Q;i++) { char st[2]; scanf("%s",st+1); if(st[1]=='A') { scanf("%d%d",&q[i].x,&q[i].y); q[i].opt=1; } if(st[1]=='D') { scanf("%d%d",&q[i].x,&q[i].y); map[q[i].x][q[i].y]=map[q[i].y][q[i].x]=1; q[i].opt=2; } if(st[1]=='Q') q[i].opt=3; } for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++) { if(map[x[i]][y[i]]==0&&findfa(x[i])!=findfa(y[i])) fa[x[i]]=y[i]; else map[x[i]][y[i]]=map[y[i]][x[i]]=0; } cnt=0; for(int i=1;i<=n;i++) if(fa[i]==i) cnt++,belong[i]=cnt; for(int i=1;i<=n;i++) { fa[i]=findfa(i); belong[i]=belong[fa[i]]; } len=0;memset(last,0,sizeof(last)); for(int i=1;i<=m;i++) { int bx=belong[x[i]],by=belong[y[i]]; if(bx!=by) { bk=false; v[bx]=i;dfs(bx,by,i); if(bk==false) cnt--; if(map[bx][by]==0) ins(bx,by),map[bx][by]=len; if(map[by][bx]==0) ins(by,bx),map[by][bx]=len; a[map[bx][by]].d++; a[map[by][bx]].d++; } } memset(v,0,sizeof(v)); for(int i=1;i<=Q;i++) { int bx=belong[q[i].x],by=belong[q[i].y]; if(q[i].opt==1) { bk=false; v[bx]=i;dfs(bx,by,i); if(bk==false) cnt--; if(map[bx][by]==0) ins(bx,by),map[bx][by]=len; if(map[by][bx]==0) ins(by,bx),map[by][bx]=len; a[map[bx][by]].d++; a[map[by][bx]].d++; } if(q[i].opt==2) { bk=false; a[map[bx][by]].d--; a[map[by][bx]].d--; v[bx]=i;dfs(bx,by,i); if(bk==false) cnt++; } if(q[i].opt==3) printf("%d\n",cnt); } return 0;}