又是玄学的一天~
首先，这题做法就很玄学，考虑到点和询问都很少，那么很多边都是没有改动的，那么可以离线用并查集缩点，然后爆搜求解。
假如只是这样还好吧，尴尬就在于我跑数据前面3个点挂了？？黑人问号
然后一怒之下特判，假如边数<10000那我就不缩点，直接爆力搞！
A了~ 真的A了。。。
这个故事告诉我们，猜证结合，爆正乱搞，天下大同。。。
#include#include #include #include #include #include using namespace std;int n,m;struct init{ int x,y,op;}h[210000],q[11000];int hlen,qlen;bool pc[5100][5100];char ss[10];void sc(){ hlen=0; memset(pc,false,sizeof(pc)); for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); if(pc[x][y]==false) { pc[x][y]=true;pc[y][x]=true; hlen++; h[hlen].x=x,h[hlen].y=y; } } scanf("%d",&qlen); for(int i=1;i<=qlen;i++) { scanf("%s",ss+1); if(ss[1]=='A') { scanf("%d%d",&q[i].x,&q[i].y),q[i].op=1; pc[q[i].x][q[i].y]=false; pc[q[i].y][q[i].x]=false; } else if(ss[1]=='D') { scanf("%d%d",&q[i].x,&q[i].y),q[i].op=2; pc[q[i].x][q[i].y]=false; pc[q[i].y][q[i].x]=false; } else q[i].op=3; }}int fa[5100];int findfa(int x){ if(fa[x]==x)return x; fa[x]=findfa(fa[x]);return fa[x];}void shrink(){ for(int i=1;i<=n;i++)fa[i]=i; if(m>10000) { for(int x=1;x<=n;x++) for(int y=1;y<=n;y++) if(pc[x][y]==true) { int fx=findfa(x),fy=findfa(y); if(fx!=fy)fa[fx]=fy; } }}//-----------init------------------------struct node{ int x,y,next;bool ch;}a[4100000];int len,last[5100];int eid[5100][5100];void ins(int x,int y){ len++; a[len].x=x;a[len].y=y; a[len].next=last[x];last[x]=len; a[len].ch=false; eid[x][y]=len;}void cut(int x,int y){ if(eid[x][y]!=-1) { a[eid[x][y]].ch=true; eid[x][y]=-1; }}//------------edge------------------------int tim,v[5100];void dfs(int x){ v[x]=tim; for(int k=last[x];k;k=a[k].next) { if(a[k].ch==false) { int y=a[k].y; if(v[y]!=tim)dfs(y); } }}int main(){ freopen("compound.in","r",stdin); freopen("compound.out","w",stdout); scanf("%d%d",&n,&m); sc();shrink(); memset(eid,-1,sizeof(eid)); for(int i=1;i<=hlen;i++) { int x=findfa(h[i].x),y=findfa(h[i].y); if(x!=y&&eid[x][y]==-1) ins(x,y), ins(y,x); } tim=0;memset(v,0,sizeof(v)); for(int i=1;i<=qlen;i++) { if(q[i].op==1) { int x=findfa(q[i].x),y=findfa(q[i].y); if(eid[x][y]==-1) ins(x,y),ins(y,x); } else if(q[i].op==2) { int x=findfa(q[i].x),y=findfa(q[i].y); cut(x,y),cut(y,x); } else { int ans=0;tim++; for(int i=1;i<=n;i++) { int x=findfa(i); if(v[x]!=tim) dfs(x), ans++; } printf("%d\n",ans); } } return 0;}