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 sccnum[next]:
continue
if not visited[next]:
id += 1
DFS(next)
visited[now] = min(visited[now],visited[next])
if visited[now]==nowid:
s = len(scc); scc.append([])
while stack:
x = stack.pop()
sccnum[x] = s; scc[-1].append(x)
if x==now:
break
def check():
for i in range(1,N+1):
if sccnum[i]==sccnum[-i]:
return
return 1
def dfs(now):
visited[now] = 1; visited[-now] = 0
for next in graph[now]:
if visited[next]==-1:
dfs(next)
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 = [[]]; sccnum = [0]*(2*N+1); stack = []
for i in range(1,N+1):
if not visited[i]:
id = 1
DFS(i)
if check():
visited = [-1]*(2*N+1); scc.reverse()
for s in scc:
for i in s:
if visited[i]==-1:
visited[i] = 0; dfs(-i)
print(1); print(*visited[1:N+1])
else:
print(0)
2-SAT 기본문제이다.
SCC + 위상정렬로 해결할 수 있다.
2-SAT - 3 [백준 11280번] 2-SAT - 3 (Python3) (tistory.com) 에서 True를 만드는 방법까지 출력한다.
2-SAT - 3을 풀었으니 쉽게 해결할 수 있을 것이라고 생각했는데, 생각보다 난관이 많은 문제였다.
풀이를 설명하면,
1. 2-SAT - 3 방식대로 scc를 구한다. (각 scc에 속한 원소들도 저장한다)
2. check 함수가 0이면 0을 출력한다.
3. check 함수가 1인 경우, 늦게 만들어진 scc 순서대로 해당 scc에 속한 원소들을 false로 두고, 그 거짓은 True로 두면서 dfs를 실행한다.
4. 원소들의 true false 여부를 출력한다.
3에서 늦게 만들어진 순서대로 하는 이유는 위상정렬에 있다. 타잔 알고리즘으로 scc를 생성하면, scc의 순서는 곧 위상정렬의 역순이 되기 때문이다. (자세한 설명은 https://m.blog.naver.com/kks227/220803009418 이곳을 참고)
2-SAT 알고리즘과, 타잔 알고리즘의 위상정렬에 대해서 알 수 있게된 좋은 문제였다.
오늘의 교훈) 2-SAT 활용문제를 풀어보자