(백준 #3977) Soccer Tactics (Python3)

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

def DFS(now):
  global id
  visited(now) = nowid = id
  stack.append(now)
  for next in graph(now):
    if not visited(next):
      id += 1
      DFS(next)
    visited(now) = min(visited(now),visited(next))
  if visited(now) == nowid:
    n = len(scc); scc.append(())
    while 1:
      x = stack.pop()
      visited(x) = 1e7
      scc(-1).append(x); sccnum(x) = n
      if x==now:
        break

for _ in range(int(input())):
  N,M = map(int,input().split())
  graph = (() for i in range(N))
  for _ in range(M):
    a,b = map(int,input().split())
    graph(a).append(b)
  
  stack = (); scc = (); visited = (0)*N; sccnum = (0)*N
  for i in range(N):
    if not visited(i):
      id = 1
      DFS(i)
  C = len(scc); indegree = (0)*C
  for i in range(N):
    for j in graph(i):
      if sccnum(i)!=sccnum(j):
        indegree(sccnum(j)) += 1
  print(*sorted(scc(indegree.index(0))) if indegree.count(0)==1 else ("Confused"),sep="\n")
  print(); input()

이것은 SCC+ 위상 정렬 문제입니다.

도미노(백준 #4196) 도미노(Python3) (tistory.com) 문제와 거의 비슷합니다.

도미노 문제가 내차수가 0인 SCC의 수를 세는 문제였다면 이 문제는 내차수가 0인 SCC가 1이면 SCC의 요소를 반환하고 SCC의 수가 1보다 크면 Confused를 반환합니다. 이다 .

오늘의 교훈) SCC 잘 활용하기