devbelly

문제 https://www.acmicpc.net/problem/5859 알고리즘 Union Find 풀이 쿼리를 순서대로 반영했을 때, 모순이 일어나지 않는 최대 갯수를 구하는 문제입니다. 유니온 파인드에서 종종 보이는 유형입니다. 하나의 사람을 두 가지 타입으로 나눕니다. $u$에 대해 참말을 하는 T(u)와 거짓말을 하는 F(u)로 나눕니다. 이에 따라 가능한 경우의 수를 묶고 모순이 발생하는지 확인하면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i > u >> v >> x; if (x == 'T') { uni(T(u), T(v)); u..