C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
int n, m, sz, color[maxn];
bool valid;
struct Node {
    int tp, val; // tp: type (0/1), val: value (0/1/2 or -j for negation)
} a[maxn];

vector<pair<int, int>> e[maxn]; // adjacency list with edges and weights
bool vis[maxn];

int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * f;
}

void init() {
    n = read();
    m = read();
    for (int i = 1; i <= n; i++) a[i] = {1, i}; // Initialize nodes
    for (int i = 1; i <= m; i++) {
        char ch;
        do {
            ch = getchar();
        } while (ch != 'T' && ch != 'F' && ch != 'U' && ch != '+' && ch != '-');

        int x, y;
        if (ch == '+') {
            x = read();
            y = read();
            a[x] = a[y];
        } else if (ch == '-') {
            x = read();
            y = read();
            if (a[y].tp) {
                a[x] = {1, -a[y].val};
            } else if (a[y].val <= 1) {
                a[x] = {0, 1 - a[y].val};
            } else {
                a[x] = {0, 2};
            }
        } else {
            x = read();
            a[x] = {0, ch == 'T' ? 0 :(ch == 'F' ? 1 : 2)} ;
        } 
    }
}

void dfs1(int u){
    ++sz;
    vis[u] = true ;
    for(auto x : e[u]) {
        int v = x.first;
        if(!vis[v]) dfs1(v);
    } 
}
void dfs2(int u) {
    ++sz;
    vis[u] = true;
    for (auto x : e[u]) {
        int v = x.first, val = x.second;
        if (!vis[v]) {
            color[v] = (color[u] ^ val);
            dfs2(v);
        } else {
            if (color[v] != (color[u] ^ val)) valid = false;
        }
    }
}

int solve() {
    for (int i = 1; i <= n; i++) e[i].clear();
    memset(vis, 0, sizeof(vis));

    for (int i = 1; i <= n; i++) {
        if (a[i].tp == 1) {
            int x = abs(a[i].val), y = (x != a[i].val);
            e[i].push_back({x, y});
            e[x].push_back({i, y});
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i].tp == 0 && !vis[i]) {
            sz = 0;
            dfs1(i);
            if (a[i].val == 2) res += sz;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            sz = 0;
            valid = true;
            color[i] = 0;
            dfs2(i);
            if (!valid) res += sz;
        }
    }

    return res;
}

int main() {
    int c = read(), t = read();
    while (t--) {
        init();
        printf("%d\n", solve());
    }
    return 0;
}