考场上乱打的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 ; }