본문 바로가기

카테고리 없음

[백준 2207번] 가위바위보 (Python3)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**4)

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 "OTL"
  return "^_^"

M,N = 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())

= [백준 11280번] 2-SAT - 3 (Python3) (tistory.com)