本文共 2375 字，大约阅读时间需要 7 分钟。

大水题来啦！！

这题的解法：

code:

#include
   
    #include
    
     #define swap(x,y) {int tt=x;x=y;y=tt;}const int N=5005;const int Q=10005;int n,m,q;bool g[N][N];//是否连通int f[N];//并查集缩点int tt[N][N],lalal;//会变的边   这条边的新编号int X[Q],Y[Q];bool ooo[Q];struct qq{    char ss[5];int x,y;}s[Q];int ff[N];int find (int x){
  return f[x]==x?f[x]:f[x]=find(f[x]);}int find1 (int x){
  return ff[x]==x?ff[x]:ff[x]=find1(ff[x]);}int ans[Q],cnt;bool ok[N];int main(){    memset(f,false,sizeof(f));    scanf("%d%d",&n,&m);    for (int u=1;u<=n;u++) f[u]=u;    for (int u=1;u<=m;u++)    {        int x,y;        scanf("%d%d",&x,&y);        if (x>y) swap(x,y);        g[x][y]=true;    }    scanf("%d",&q);    memset(tt,-1,sizeof(tt));    for (int u=1;u<=q;u++)    {        scanf("%s",s[u].ss);        if (s[u].ss[0]=='Q') continue;        scanf("%d%d",&s[u].x,&s[u].y);        if (s[u].x==s[u].y) {u--;q--;continue;}        if (s[u].x>s[u].y) swap(s[u].x,s[u].y);        g[s[u].x][s[u].y]=(s[u].ss[0]=='A');        if (tt[s[u].x][s[u].y]==-1)        {            tt[s[u].x][s[u].y]=++lalal;            X[lalal]=s[u].x;Y[lalal]=s[u].y;        }    }       for (int u=1;u<=n;u++)    {        for (int i=u+1;i<=n;i++)        {            if (g[u][i]==true&&tt[u][i]==-1)            {                int fx=find(u),fy=find(i);                if (fx==fy) continue;                f[fx]=fy;            }        }    }    for (int u=1;u<=lalal;u++)  ooo[u]=g[X[u]][Y[u]];    cnt=0;    memset(ok,false,sizeof(ok));    for (int O=q;O>=1;O--)    {        if (s[O].ss[0]=='Q')        {            cnt++;ans[cnt]=0;            for (int i=1;i<=n;i++) ff[i]=f[i];            for (int i=1;i<=lalal;i++)            {                if (ooo[i]==true)                {                    int fx=find1(X[i]),fy=find1(Y[i]);                    if (fx==fy) continue;                    ff[fx]=fy;                }            }            for (int u=1;u<=n;u++) ok[find1(u)]=true;            for (int u=1;u<=n;u++)                if (ok[u])                {                    ans[cnt]++;                    ok[u]=false;                }        }        else ooo[tt[s[O].x][s[O].y]]=!(s[O].ss[0]=='A');    }    for (int u=cnt;u>=1;u--) printf("%d\n",ans[u]);    return 0;}