[백준 3648번] 아이돌 (Python3)

import sys
input = sys.stdin.readline

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 "no"
  return "yes"

while 1:
  try:
    N,M = map(int,input().split())
  except:
    break
  graph = [[] for i in range(2*N+1)]
  graph[-1] = [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 [백준 11280번] 2-SAT - 3 (Python3) (tistory.com) 응용문제

명제를 하나 더 추가한다는 아이디어가 핵심이며, 생각하기 어려웠다.

 

1번이 무조건 참이어야 하므로 (1V1)이 하나 더 들어간다고 생각하면 2-SAT - 3과 똑같은 코드로 해결할 수 있다.

 

 

여담) 내 풀이가 파이썬 기준 성능 1위가 되었다.