import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
def DFS(now):
global id,s
visited[now] = nowid = id
stack.append(now)
for next in graph[now]:
if scc[next]:
continue
if not visited[next]:
id += 1
DFS(next)
visited[now] = min(visited[now],visited[next])
if visited[now]==nowid:
s += 1
while stack:
x = stack.pop()
scc[x] = s
if x==now:
break
def check():
for i in range(1,N+1):
if scc[i]==scc[-i]:
return 0
return 1
N,M = map(int,input().split())
graph = [[] for i in range(2*N+1)]
for _ in range(M):
a,b = map(int,input().split())
graph[-a].append(b)
graph[-b].append(a)
visited = [0]*(2*N+1); scc = [0]*(2*N+1); stack = []; s = 0
for i in range(1,N+1):
if not visited[i]:
id = 1
DFS(i)
print(check())
2-SAT 기본문제이다.
SCC로 해결할 수 있다.
풀이를 설명하면,
1. a,b가 입력으로 주어질 때, -a가 참이면 (즉 a가 거짓이면) b가 무조건 참이어야 한다. 마찬가지로 -b가 참이면 a가 무조건 참이어야 한다. 이를 그래프로 표현한다.
2. 그래프의 간선을 따라 타잔알고리즘으로 scc를 찾는다.
3. 같은 scc 안에 어떤 값 x에 대해 x가 참일때와 거짓일 때(+x와 -x)가 동시에 포함되어 있으면 0을 출력하고 그렇지 않으면 1을 출력한다. (x가 참이면서 동시에 거짓일 수 없으므로)
SAT 문제가 무엇인지와 어떻게 해결하는지를 배울 수 있는 좋은 문제였다.
오늘의 교훈) SAT를 활용한 문제들도 풀어보자