rt

并查集做法，大概就是先给每个 $i$ 赋个初始点，然后每次操作时，给 $i$ 重新赋一个点，统计答案是只看最后赋的点和初始点之间的关系。

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;
int c,t,n,m,tot=1,p1,p2,p3;
int fa[800010],to[100001],be[100001];

int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); }

int main() {
//	freopen("b.in","r",stdin);
//    freopen("b.out","w",stdout);
    scanf("%d%d",&c,&t);
    while (t--) {
        memset(fa,0,sizeof fa);
        tot=1;
        scanf("%d%d",&n,&m);
        p1=++tot,p2=++tot,p3=++tot;
        fa[p1]=p1,fa[p2]=p2,fa[p3]=p3;
        for (int i=1;i<=n;i++) be[i]=to[i]=(tot+=2),fa[tot]=tot,fa[tot^1]=tot^1;
        for (int i=1,x,y;i<=m;i++) {
            char ch;
            cin>>ch;
            scanf("%d",&x);
            to[x]=(tot+=2),fa[tot]=tot,fa[tot^1]=tot^1;
            if (ch=='T') {
                fa[find(to[x])]=find(p1);
                fa[find(to[x]^1)]=find(p2);
            } else if (ch=='F') {
                fa[find(to[x])]=find(p2);
                fa[find(to[x]^1)]=find(p1);
            } else if (ch=='U') {
                fa[find(to[x])]=find(p3);
                fa[find(to[x]^1)]=find(p3);
            } else if (ch=='+') {
                scanf("%d",&y);
                fa[find(to[x])]=find(to[y]);
                fa[find(to[x]^1)]=find(to[y]^1);
            } else {
                scanf("%d",&y);
                fa[find(to[x])]=find(to[y]^1);
                fa[find(to[x]^1)]=find(to[y]);
            }
        }
        int ans=0;
        for (int i=1;i<=n;i++) fa[find(to[i])]=find(be[i]),fa[find(to[i]^1)]=find(be[i]^1);
        for (int i=1;i<=n;i++) ans+=find(to[i])==find(to[i]^1);
        printf("%d\n",ans);
    }
    return 0;
}