Description
科学家最近发现了一种高分子有机化合物 SHTSC。这种物质的分子由单个或多个原子组成,原子之间通过化学键相互连接。SHTSC 十分不稳定,其原子之间的化学键经常会伴随着炫酷的声音特效和光影效果发生断裂或者重新连接。 然而,令科学家们大为惊异的是,SHTSC 在变化过程中始终保持着一种特殊的性质:即不存在这样的原子序列 a1,a2,…,an(n>3)满足 a1 与 a2、a2 与 a3、……、an-1 与 an 以及 an 与 a1 都通过化学键相连,但它们之间却没有其他化学键相连的情况。现在科学家将 SHTSC 的原子由 1 到 n 标号,并告诉你 SHTSC 的初始形态以及原子之间的化学键变化情况,他们想知道在实验过程中的某些时刻 SHTSC 分裂成了多少个分子?
Input
第一行两个整数:n, m。表示 SHTSC 的总原子个数以及初始的化学键数。 从第二行开始的 m 行,每行两个整数 a, b (1≤a,b≤n)。表示编号为 a, b 的两 个原子在初始状态中有化学键相连。数据保证每对 a, b 只出现一次。 第 m+2 行有一个整数:q。表示实验的总操作数。 之后 q 行中的每一行为以下三种操作当中的一种: 1、A i j 表示 i 号原子与 j 号原子之间形成了一条新的化学键; 2、D i j 表示 i 号原子与 j 号原子之间原有的化学键断裂了; 3、Q 询问当前 SHTSC 分裂成了多少个不同的分子。 数据保证所有的实验操作都是合法的。
Output
对于每个 Q 操作,输出一行一个整数,为相应时刻的分子个数。
Sample Input
7 10
1 2
2 3
3 4
4 1
1 3
2 4
5 6
6 7
7 5
2 5
10
Q
D 2 5
Q
D 5 6
D 5 7
Q
A 2 5
Q
A 5 6
Q
Sample Output
1
2
3
2
1
HINT
对于 100%的数据, n≤5000,m≤200000,q≤10000。
题解
真的是神奇的做法 观察到数据中q很小而m很大，所以其实自始至终有很多条边都是没有用过的 于是我们可以把这些边弄出来，并查集缩点 之后的询问直接暴力dfs求解，暴力连边暴力删边 跑的挺快的
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; int n,m,Q; struct Ask{int u,v,op;}A[11000]; struct edge{int x,y;bool bk;edge(){bk=false;}}e[210000]; bool cmp(edge n1,edge n2) { if(n1.x!=n2.x)return n1.x<n2.x; return n1.y<n2.y; } int fd(int x,int y) { int l=1,r=m; while(l<=r) { int mid=(l+r)/2; if(e[mid].x<x)l=mid+1; else if(e[mid].x>x)r=mid-1; else if(e[mid].y<y)l=mid+1; else if(e[mid].y>y)r=mid-1; else return mid; } return -1; } struct node { int x,y,next,nx,ny,other; bool bk; node(){bk=true;} }a[450000];int len,last[5100]; void ins(int x,int y,int nx,int ny) { int k1,k2; k1=++len; a[len].x=x;a[len].y=y;a[len].nx=nx;a[len].ny=ny; a[len].next=last[x];last[x]=len; k2=++len; a[len].x=y;a[len].y=x;a[len].nx=nx;a[len].ny=ny; a[len].next=last[y];last[y]=len; a[k1].other=k2;a[k2].other=k1; } bool v[5100]; char ch[10]; int fa[5100],belong[5100],seg[5100],cnt; int findfa(int x) { if(fa[x]!=x)fa[x]=findfa(fa[x]); return fa[x]; } void dfs(int x) { for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(v[y]==false && a[k].bk)v[y]=true,dfs(y); } } void del(int P) { int x=A[P].u,y=A[P].v; int u=belong[x],v=belong[y]; for(int k=last[u];k;k=a[k].next) if(a[k].y==v && a[k].nx==x && a[k].ny==y && a[k].bk) { a[k].bk=a[a[k].other].bk=false; return ; } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){scanf("%d%d",&e[i].x,&e[i].y);if(e[i].x>e[i].y)swap(e[i].x,e[i].y);} sort(e+1,e+1+m,cmp); scanf("%d",&Q); for(int i=1;i<=Q;i++) { scanf("%s",ch+1); if(ch[1]=='Q'){A[i].op=2;continue;} scanf("%d%d",&A[i].u,&A[i].v);if(A[i].u>A[i].v)swap(A[i].u,A[i].v); if(ch[1]=='A')A[i].op=0; else A[i].op=1; int tmp=fd(A[i].u,A[i].v);if(tmp==-1)continue; e[tmp].bk=true; } for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=m;i++) if(e[i].bk==false) { int p=findfa(e[i].x),q=findfa(e[i].y); if(p!=q)fa[p]=q; } cnt=0; for(int i=1;i<=n;i++)if(fa[i]==i)seg[i]=++cnt; for(int i=1;i<=n;i++)belong[i]=seg[findfa(i)]; for(int i=1;i<=m;i++) if(e[i].bk==true)ins(belong[e[i].x],belong[e[i].y],e[i].x,e[i].y); for(int i=1;i<=m;i++) { int p=findfa(e[i].x),q=findfa(e[i].y); if(p!=q)fa[p]=q,cnt--; } int ans=cnt; for(int i=1;i<=Q;i++) { if(A[i].op==2)printf("%d\n",ans); else if(A[i].op==0) { memset(v,false,sizeof(v));v[belong[A[i].u]]=true; dfs(belong[A[i].u]); if(v[belong[A[i].v]]==false)ans--; ins(belong[A[i].u],belong[A[i].v],A[i].u,A[i].v); } else { del(i); memset(v,false,sizeof(v));v[belong[A[i].u]]=true; dfs(belong[A[i].u]); if(v[belong[A[i].v]]==false)ans++; } } return 0; }