[백준 5859] 거짓말쟁이

문제

www.acmicpc.net/problem/5859

알고리즘

union find

풀이

쿼리를 순서대로 반영했을 때, 모순이 일어나지 않는 최대 갯수를 구하는 문제입니다.

유니온 파인드에서 종종 보이는 유형입니다. 하나의 사람을 두 가지 타입으로 나눕니다. $u$에 대해 참말을 하는 T(u)와 거짓말을 하는 F(u)로 나눕니다. 이에 따라 가능한 경우의 수를 묶고 모순이 발생하는지 확인하면 됩니다.

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

#define T(x) (x << 1)
#define F(x) (x << 1 | 1)
const int MAXN = 1e3 + 5;

int N, M, u, v, ans, p[MAXN << 1];
char x;

int find(int x) {
    return (p[x] < 0 ? x : p[x] = find(p[x]));
}
void uni(int a, int b) {
    int pa = find(a);
    int pb = find(b);
    if (pa ^ pb)
        p[pa] = pb;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    memset(p, -1, sizeof(p));
    cin >> N >> M;
    rep(i, M) {
        cin >> u >> v >> x;
        if (x == 'T') {
            uni(T(u), T(v));
            uni(F(u), F(v));
        } else {
            uni(T(u), F(v));
            uni(F(u), T(v));
        }
        if (find(T(u)) ^ find(F(u))) {
            ans += 1;
        } else {

            break;
        }
    }
    cout << ans;
    return 0;
}