Descrição do Problema

Em lógica de três valores, uma variável pode assumir os valores Verdadeiro (T), Falso (F) ou Desconhecido (U). A operação lógica de negação é definida como: ¬T = F, ¬F = T, ¬U = U.

Dado n variáveis x1, ..., xn, existem m instruções executadas sequencialmente, de três tipos possíveis: atribuição direta de T, F ou U; atribuição de outra variável; ou atribuição da negação de outra variável. O objetivo é encontrar a atribuição inicial que minimize o número de variáveis U, garantindo que após executar todas as instruções, os valores finais sejam iguais aos iniciais. É garantido que pelo menos uma solução válida existe.

Formato de Entrada

A entrada contém múltiplos casos de teste. A primeira linha tem dois inteiros c e t, indicando o identificador do teste e o número de casos. Para cada caso:

• Primeira linha: inteiros n e m, representando o número de variáveis e instruções.
• m linhas seguintes: cada instrução começa com um caractere v entre 'T', 'F', 'U', '+' ou '-'. Se v for 'T', 'F' ou 'U', segue-se um inteiro i, indicando xi ← v. Se v for '+', seguem-se inteiros i e j, indicando xi ← xj. Se v for '-', seguem-se inteiros i e j, indicando xi ← ¬xj.

Formato de Saída

Para cada caso de teste, imprima um único inteiro: o número mínimo de variáveis U em uma solução válida.

Exemplo

Entrada de teste 1:

1 3
3 3
- 2 1
- 3 2
+ 1 3
3 3
- 2 1
- 3 2
- 1 3
2 2
T 2
U 2

Saída esperada:

0
3
1

Explicação do Exemplo

No primeiro caso, as instruções são x2 ← ¬x1, x3 ← ¬x2, x1 ← x3. Uma solução viável é x1=T, x2=F, x3=T, com 0 variáveis U.

No segundo caso, as instruções são x2 ← ¬x1, x3 ← ¬x2, x1 ← ¬x3. A única solução é x1=x2=x3=U, resultando em 3 variáveis U.

No terceiro caso, as instruções são x2 ← T e x2 ← U. Uma solução ótima é x1=T, x2=U, com 1 variável U.

Restrições

Para todos os testes: 1 ≤ t ≤ 6, 1 ≤ n, m ≤ 10^5. Os testes são categorizados conforme a tabela abaixo:

Abordagem

O problema pode ser modelado utilizando uma estrutura de dados Union-Find (união-busca) adaptada para lidar com os três valores lógicos. As variáveis são tratadas como nós em um grafo, onde as instruções definem relações de igualdade ou negação. A ideia é determinar componentes conectados e verificar a consistência das atribuições, minimizando ocorrências de U.

Implementação

Abaixo está uma implementação em C++ que utiliza Union-Find com caminhamento otimizado. As variáveis são representadas por índices, e operações especiais são usadas para representar T, F e U.

#include <iostream>
#include <vector>
using namespace std;

const int MAX_NODES = 100005;
const int TRUE_VAL = 100001;   // Representa T
const int FALSE_VAL = -100001; // Representa F
const int UNK_VAL = 0;         // Representa U

int parent[MAX_NODES];
bool visited[300005];

int find(int x) {
    if (x == TRUE_VAL || x == FALSE_VAL) return x;
    if (x == UNK_VAL || visited[x + MAX_NODES]) return UNK_VAL;
    if (visited[-x + MAX_NODES]) return TRUE_VAL; // Lógica para negação
    if (x < 0) {
        if (x == -parent[-x]) return x;
        visited[x + MAX_NODES] = true;
        int res = find(-parent[-x]);
        visited[x + MAX_NODES] = false;
        return res;
    }
    if (x == parent[x]) return x;
    visited[x + MAX_NODES] = true;
    int res = find(parent[x]);
    parent[x] = res;
    visited[x + MAX_NODES] = false;
    return res;
}

int main() {
    int c, t;
    cin >> c >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; ++i) parent[i] = i;
        for (int i = 0; i < m; ++i) {
            char op;
            int a, b;
            cin >> op;
            if (op == 'T') {
                cin >> a;
                parent[a] = TRUE_VAL;
            } else if (op == 'F') {
                cin >> a;
                parent[a] = FALSE_VAL;
            } else if (op == 'U') {
                cin >> a;
                parent[a] = UNK_VAL;
            } else if (op == '+') {
                cin >> a >> b;
                parent[a] = parent[b];
            } else { // op == '-'
                cin >> a >> b;
                parent[a] = -parent[b];
            }
        }
        int unknownCount = 0;
        for (int i = 1; i <= n; ++i) {
            if (find(i) == UNK_VAL) unknownCount++;
        }
        cout << unknownCount << endl;
    }
    return 0;
}