BOJ 5859 Liars and Truth Tellers

https://www.acmicpc.net/problem/5859

5859번: Liars and Truth Tellers

 

문제를 잘 보면 쿼리가 T일 경우 두 소 모두 진실을 말하거나 거짓을 말하고 있고 쿼리가 F일 경우 한 소는 진실을, 한 소는 거짓을 말하고 있습니다. 따라서 T일 경우 두 정점이 같은 그룹에 속해야 하고 F일 경우 두 정점이 다른 그룹에 속해야 합니다.

 

이를 구하기 위해 SAT의 아이디어를 빌렸습니다. 소 $A$가 진실을 말하는 경우를 정점 $A$, 거짓을 말하는 경우를 정점 $A+N$으로 두면 총 $2N$개의 정점이 생기게 됩니다. 그리고 두 정점이 모두 진실이거나 모두 거짓이어야 하는 경우끼리 묶어 간선으로 연결해줍니다. 소 $u$와 $v$에 대해 쿼리가 T라면 정점 $u$와 $v$가 이어지고 정점 $u+N$과 $v+N$이 이어지는 식입니다. 반대로 쿼리가 F라면 정점 $u$와 $v+N$이 이어지고 정점 $u+N$과 $v$가 이어집니다.

 

이 때 특정 쿼리를 수행한 이후 어떤 소 $i$에 대하여 정점 $i$와 정점 $i+N$가 연결되어 있는 경우 모순이 발생하기 때문에 해당 쿼리 이전까지가 답이 됩니다.

 

아래는 코드입니다.

 

#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '

std::vector<int> UF;

void UF_init(int sz)
{
    UF.resize(sz + 1);
    for (int i = 1; i < UF.size(); i++)
        UF[i] = i;
}

int Find(int x)
{
    if (UF[x] == x) return x;
    else return UF[x] = Find(UF[x]);
}

void Union(int x, int y)
{
    x = Find(x);
    y = Find(y);
    UF[y] = x;
}

using namespace std;

int T, n, m;

int32_t main(void) {
  FastIO;
  T = 1;
  //cin >> T;

  while (T--) {
    cin >> n >> m;

        UF_init(2 * n);

        int ans = 0;

        for (int i = 0; i < m; i++) {
            int a, b;
            char c;
            cin >> a >> b >> c;

            if (c == 'T') {
                Union(a, b);
                Union(a + n, b + n);
            }
            else {
                Union(a, b + n);
                Union(a + n, b);
            }

            if (Find(a) == Find(a + n) || Find(b) == Find(b + n)) break;

            ans = i + 1;
        }

        cout << ans << endl;
  }

  return 0;
}