[백준 3977번] 축구 전술 (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) 문제와 거의 유사하다.

 

도미노 문제가 indegree가 0인 SCC의 개수를 세어주는 문제였다면, 이 문제는 indegree가 0인 SCC가 1개이면 해당 SCC의 요소를 출력하고, SCC가 1개보다 많으면 Confused를 출력해주면 된다.

 

 

오늘의 교훈) SCC를 잘 활용하자