这段代码不应该O(n+m)吗 统计每个变量最终对应TFU或某个变量,用2-SAT做求对应点处于相同强连通分量数即为答案,但是T了3个点,有dalao能解答吗,感激不尽
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int rxcoffee,T,n,m,a[N],h[2*N],nx[2*N],b[2*N],tt,dfn[2*N],low[2*N],sjc,ans,zhan[2*N],top,cnt,c[2*N];
bool pd[2*N];
void zj(int x,int y)
{
b[++tt]=y;
nx[tt]=h[x];
h[x]=tt;
}
void tarjan(int x)
{
dfn[x]=low[x]=++sjc;
pd[x]=true;zhan[++top]=x;
for(int i=h[x];i;i=nx[i])
{
int y=b[i];
if(!dfn[y])
{
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(pd[y])
low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x])
{
++cnt;
int z;
do
{
z=zhan[top--];
pd[z]=false;
c[z]=cnt;
}while(x!=z);
}
}
int main()
{
scanf("%d%d",&rxcoffee,&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
a[i]=i;
sjc=0;
ans=0;
tt=0;
cnt=0;
top=0;
memset(dfn,0,sizeof(dfn));
memset(pd,false,sizeof(pd));
memset(h,0,sizeof(h));
memset(nx,0,sizeof(nx));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
for(int i=1;i<=m;i++)
{
char s[2];
int x,y;
scanf("%s",s);
if(s[0]=='+')
{
scanf("%d%d",&x,&y);
a[x]=a[y];
}
else if(s[0]=='-')
{
scanf("%d%d",&x,&y);
a[x]=-a[y];
}
else
{
scanf("%d",&x);
if(s[0]=='T')
a[x]=N;
else if(s[0]=='F')
a[x]=-N;
else
a[x]=0;
}
}
for(int i=1;i<=n;i++)
{
if(a[i]==0)
zj(i,i+n),zj(i+n,i);
else if(a[i]==N)
zj(i+n,i);
else if(a[i]==-N)
zj(i,i+n);
else if(a[i]>0)
zj(i,a[i]),zj(a[i],i),zj(i+n,a[i]+n),zj(a[i]+n,i+n);
else
zj(i,-a[i]+n),zj(-a[i]+n,i),zj(i+n,-a[i]),zj(-a[i],i+n);
}
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i);
for(int i=1;i<=n;i++)
if(c[i]==c[i+n])
++ans;
printf("%d\n",ans);
}
return 0;
}