[BOJ 2416] 문

문제

---

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

풀이

---

각 수로에서 한 문이 열린 상태라면 다른 문은 무조건 닫힌 상태여야 한다.

그러므로 각 수로마다 2개의 간선을 추가시키면 된다.

타잔 알고리즘을 이용한 풀이는 MLE가 떠서 코사라주 알고리즘을 이용한 풀이로 AC를 받았다.

코드

---

import sys

n, m = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(2 * m + 1)]
reverse = [[] for _ in range(2 * m + 1)]

for _ in range(n):
    a, s, b, t = map(int, sys.stdin.readline().split())
    graph[(-1) ** s * a].append(-(-1) ** t * b)
    graph[(-1) ** t * b].append(-(-1) ** s * a)
    reverse[-(-1) ** t * b].append((-1) ** s * a)
    reverse[-(-1) ** s * a].append((-1) ** t * b)

stack = []
visit = [0] * (2 * m + 1)
for i in range(1, 2 * m + 1):
    if not visit[i]:
        visit[i] = 1
        queue = [i]
        while queue:
            cur = queue[-1]
            for nxt in graph[cur]:
                if not visit[nxt]:
                    visit[nxt] = 1
                    queue.append(nxt)
                    break
            else:
                stack.append(queue.pop())

scc_num = 0
scc_idx = [0] * (2 * m + 1)
finish = [0] * (2 * m + 1)
while stack:
    node = stack.pop()
    if not finish[node]:
        finish[node] = 1
        queue = [node]
        while queue:
            cur = queue[-1]
            for nxt in reverse[cur]:
                if not finish[nxt]:
                    finish[nxt] = 1
                    queue.append(nxt)
                    break
            else:
                scc_idx[queue.pop()] = scc_num

        scc_num += 1

res = [0] * (m + 1)
for i in range(1, m + 1):
    if scc_idx[i] == scc_idx[-i]:
        print('IMPOSSIBLE')
        break
    if scc_idx[i] > scc_idx[-i]:
        res[i] = 1
else:
    for j in range(1, m + 1):
        print(res[j])