사랑과 전쟁

• 문제 상황이 아주 대환장파티.. 최대 30쌍의 부부가 모였는데 최대 50쌍의 불륜관계가 있다고 한다.. 한명이 여러명과 불륜을 하는 관계가 다수라는 말이고.. 거기에다가 불륜은 이성간 동성간을 가리지 않고 일어난다고 한다..ㄷㄷㄷ 어떻게 보면 PC에 충실한건가..
• 암튼 문제 상황을 이해하려 하지 말고, 그냥 문제를 풀려고 하면. 상황을 2-sat으로 모델링할수 있다. 커플마다 불리언 변수를 만들고, i번째 커플에 대해서 {i}h가 0w과 같은쪽에 있으면 x_i=True, {i}w가 0w와 같은쪽에 있으면 x_i=False 이런식으로 값을 갖도록 정의한다. 예를 들어 {i}h와 j{w}가 불륜이라면, 둘이 동시에 0h쪽에 있어서는 안되므로, 둘중 적어도 한명은 0w쪽에 있어야 하고, 이것은 x_i or ~x_j 로 쓸수 있다.
• 처음에 0번 커플을 제외한 N-1개의 커플에 대해서 식을 세워서 처리하다가 몇번 맞왜틀을 겪었고.. 그렇게 발견한 중요한 사실은 철승이나 보람이도 불륜에 포함될수 있다는 것.. N개의 변수를 모두 만들어야 하고, x_0은 언제나 False가 되도록 조건을 하나더 추가해줘야 한다,
• 총 시간복잡도는 O(N+M)

"""Solution code for "BOJ 4230. 사랑과 전쟁".

- Problem link: https://www.acmicpc.net/problem/4230
- Solution link: http://www.teferi.net/ps/problems/boj/4230

Tags: [2-sat]
"""

import sys
from teflib import twosat


def main():
    while (line := sys.stdin.readline().rstrip()) != '0 0':
        N, M = [int(x) for x in line.split()]
        two_sat = twosat.TwoSat(N)
        two_sat.x_is_true(~0)
        for _ in range(M):
            x, y = sys.stdin.readline().split()
            x = int(x[:-1]) if x[-1] == 'h' else ~int(x[:-1])
            y = int(y[:-1]) if y[-1] == 'h' else ~int(y[:-1])
            two_sat.x_or_y(x, y)

        try:
            assignment = two_sat.find_truth_assignment()
        except ValueError:
            print('bad luck')
        else:
            answer = ' '.join(
                f'{i}{"h" if x else "w"}'
                for i, x in enumerate(assignment[1:], start=1)
            )
            print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.twosat.TwoSat