[BOJ 4230] 사랑과 전쟁

문제

---

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

풀이

---

보람이쪽에 앉는 것을 True, 철승이쪽에 앉는 것을 False라고 하면, 각 부부 a, b에 대해 a -> !b, !a -> b, b -> !a, !b -> a이다.

또한 불륜 커플 c, d에 대해 !c -> d, !d -> c를 만족해야 한다.

코드

---

import sys


def dfs(cur):
    global idx, scc_num
    visit[cur] = idx
    low = idx
    idx += 1
    stack.append(cur)

    for nxt in graph[cur]:
        if not visit[nxt]:
            low = min(low, dfs(nxt))
        elif not finish[nxt]:
            low = min(low, visit[nxt])

    if low == visit[cur]:
        while stack:
            top = stack.pop()
            finish[top] = 1
            scc_idx[top] = scc_num
            if cur == top:
                break

        scc_num += 1

    return low


while True:
    n, m = map(int, sys.stdin.readline().split())
    if (n, m) == (0, 0):
        break

    graph = [[] for _ in range(4 * n + 1)]

    graph[1].append(-1)
    graph[-2].append(2)
    
    for i in range(2, n + 1):
        graph[2 * i - 1].append(-2 * i)
        graph[2 * i].append(-2 * i + 1)
        graph[-2 * i + 1].append(2 * i)
        graph[-2 * i].append(2 * i - 1)
    
    for _ in range(m):
        a, b = sys.stdin.readline().split()
        a = 2 * int(a[:-1]) + 1 + (a[-1] == 'w')
        b = 2 * int(b[:-1]) + 1 + (b[-1] == 'w')
        graph[-a].append(b)
        graph[-b].append(a)
    
    stack = []
    scc_num = 1
    scc_idx = [0] * (4 * n + 1)
    finish = [0] * (4 * n + 1)
    visit = [0] * (4 * n + 1)
    idx = 1

    for i in range(1, 4 * n + 1):
        if not visit[i]:
            dfs(i)

    res = [0] * (2 * n + 1)
    for i in range(1, 2 * n + 1):
        if scc_idx[i] == scc_idx[-i]:
            print('bad luck')
            break
        if scc_idx[i] < scc_idx[-i]:
            res[i] = 1
    else:
        for i in range(3, 2 * n + 1):
            if res[i]:
                print(str((i - 1) // 2) + 'wh'[i % 2], end=' ')
        print()