2023NOIP T2

考场上乱打的40

并查集可做。

点的修改其实就是新建一个点，最后点的编号要和最初的点在一个组。

有个坑，自己可以和自己取反。也不算坑吧，写代码的时候没注意到。

还是有很多技巧，只能说经验不足。

#include <bits/stdc++.h>
using namespace std ;
const int N = 500005 ;
int n, m, fa[N], pos[N], c, t, T, F, U, tot, ans = 0, cnt = 0 ;
char s[2] ;int findset(int x)
{
    if(x == fa[x]) return x ;
    return fa[x] = findset(fa[x]) ; 
}
void unionset(int a, int b)
{
    int x = findset(a), y = findset(b) ;
    if(x == y) return ;
    fa[x] = y ;
    return ;
}
int main()
{
    //freopen("tribool3.in", "r", stdin) ;
    //freopen("tribool3.out", "w", stdout) ;
    scanf("%d%d", &c, &t) ;
    while(t --)
    {
        scanf("%d%d", &n, &m) ;
        cnt = n ;
        tot = n + m ;
        T = tot * 2 + 1, F = tot * 2 + 2 , U = tot * 2 + 3 ; 
        for(int i = 1; i <= tot * 2 + 3 ; i ++) fa[i] = i ;
        for(int i = 1; i <= n; i ++) pos[i] = i ;
        for(int i = 1; i <= m; i ++)
        {
            scanf("%s", s) ;
            int a, b ;
            scanf("%d", &a) ; 
            if(s[0] == 'T' || s[0] == 'F' || s[0] == 'U')
            {
                pos[a] = ++cnt ;
                if(s[0] == 'T') unionset(pos[a], T), unionset(pos[a] + tot, F) ;
                if(s[0] == 'F') unionset(pos[a], F), unionset(pos[a] + tot, T) ;
                if(s[0] == 'U') unionset(pos[a], U), unionset(pos[a] + tot, U) ;
            }
            else if(s[0] == '+')
            {
                scanf("%d", &b) ;
                int y = pos[b] ;
                pos[a] = ++cnt ;
                unionset(pos[a], y) ;
                unionset(pos[a] + tot, y + tot) ;
            }
            else if(s[0] == '-')
            {
                scanf("%d", &b) ;
                int y = pos[b] ;
                pos[a] = ++cnt ;
                unionset(pos[a], y + tot) ;
                unionset(pos[a] + tot, y) ;
            }
        }
        for(int i = 1; i <= n; i ++){
            unionset(i, pos[i]) ;
            unionset(i + tot, pos[i] + tot) ;
        }
        for(int i = 1; i <= n; i ++) 
        {
            if(findset(i) == findset(i + tot))
            {
                unionset(i, U) ;
            }
        }
        ans = 0 ;
        for(int i = 1; i <= n; i ++) 
        {
            if(findset(i) == findset(U)) ans ++ ;
        }
        printf("%d\n", ans) ;
    }
    return 0 ;
}