• 기본적인 2-SAT 문제이다. 입력으로 들어오는 두 변수들의 페어를 그대로 or절로 만들고, 절들을 and해서 식을 만들면 끝. 시간복잡도는 O(N+M).
• 하지만 이 문제는 입력데이터를 처리하는데에 매우 골치가 아프다. 대충 듣기에는 공백으로 구분되는 입력값들이 실제로는 아무 whitespace들로 구분되는것 같다. whitespace 단위로 입력을 받는 cpp는 아무 문제가 없겠지만, line단위로 입력받는 파이썬은 이것때문에 꼬인다. 전체 데이터를 한번에 입력받아서 처리하는 식으로 어찌어찌 구현했다.

"""Solution code for "BOJ 3747. 완벽한 선거!".

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

Tags: [2-sat]
"""

import sys
from teflib import twosat


def main():
    inp = iter(sys.stdin.read().split())
    while True:
        try:
            N = int(next(inp))
        except StopIteration:
            break
        two_sat = twosat.TwoSat(N)
        M = int(next(inp))
        for _ in range(M):
            x, y = (int(next(inp)), int(next(inp)))
            x = x - 1 if x > 0 else x
            y = y - 1 if y > 0 else y
            two_sat.x_or_y(x, y)
        print('1' if two_sat.is_satisfiable() else '0')


if __name__ == '__main__':
    main()

• Dependency: teflib.twosat.TwoSat