洛谷数据100,官方数据90,第10个点的第2个第4个错了。求助。代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct xx{
int x,c;
}fx,fy,f[N];
int c,t,i,n,m,x,y,ans,p[N],fa[N],co[N];
char op;
char read(){
char ch=getchar();
while(ch!='T'&&ch!='F'&&ch!='U'&&ch!='+'&&ch!='-')ch=getchar();
return ch;
}
xx find(int x){
if(f[x].x==x)return f[x];
xx y=find(f[x].x);
f[x].x=y.x;f[x].c^=y.c;
return f[x];
}
int main(){
scanf("%d%d",&c,&t);
while(t--){
ans=0;memset(p,0,sizeof(p));memset(co,0,sizeof(co));memset(f,0,sizeof(f));
scanf("%d%d",&n,&m);
for(i=1;i<=n+3;i++)fa[i]=i,f[i].x=i;
for(i=1;i<=m;i++){
op=read();
if(op=='T'){
scanf("%d",&x);
fa[x]=n+1;co[i]=0;
}else if(op=='F'){
scanf("%d",&x);
fa[x]=n+3;co[x]=0;
}else if(op=='U'){
scanf("%d",&x);
fa[x]=n+2;co[x]=0;
}else if(op=='+'){
scanf("%d%d",&x,&y);
fa[x]=fa[y];co[x]=co[y];
}else{
scanf("%d%d",&x,&y);
fa[x]=fa[y];co[x]=1-co[y];
}
}
for(i=1;i<=n;i++){
fx=find(i);fy=find(fa[i]);
f[fx.x].x=fy.x;f[fx.x].c^=fy.c^co[i];
}
for(i=1;i<=n;i++)f[i]=find(f[i].x);
for(i=1;i<=n;i++)
if(f[i].x==n+2||f[i].x==i&&f[i].c)p[i]=1;
for(i=1;i<=n;i++)
if(f[i].x<=n)p[i]=p[f[i].x];
for(i=1;i<=n;i++)ans+=p[i];
printf("%d\n",ans);
}
return 0;
}