[백준 6543번] 그래프의 싱크 (Python3)

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

def DFS(now):
  global id
  nowid = visited[now] = 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:
    n = len(scc); scc.append([])
    while 1:
      x = stack.pop()
      sccnum[x] = n; scc[-1].append(x)
      if x==now:
        break

while 1:
  try:
    N,M = map(int,input().split())
  except:
    break
  data = [*map(int,input().split())]
  
  graph = [[] for i in range(N+1)]
  for i in range(M):
    graph[data[i*2]].append(data[i*2+1])

  scc,stack = [[]],[]; n = 0
  sccnum,visited,outdegree = [[0]*(N+1) for i in range(3)]

  for i in range(1,N+1):
    if not visited[i]:
      id = 1
      DFS(i)
  
  outdegree = [0]*(N+1)
  for i in range(1,N+1):
    for j in graph[i]:
      if sccnum[i]!=sccnum[j]:
        outdegree[sccnum[i]] += 1
  result = []
  for i in range(1,len(scc)):
    if not outdegree[i]:
      result += scc[i]
  print(*sorted(result))

SCC 응용문제.

도미노 [백준 4196번] 도미노 (Python3) (tistory.com) 와 거의 유사한 문제이다. 도미노가 indegree가 0인 개수를 구하는 문제였다면, 이 문제는 outdegree가 0인 scc를 구하면 된다.

 

즉, 풀이를 요약하면,

1. 타잔알고리즘으로 SCC를 구한다.

2. 각 SCC의 outdegree를 구한다.

3. outdegree가 0인 SCC의 노드를 출력한다.

 

로 정리할 수 있다.

 

풀이 자체는 간단한 문제였는데, outdegree라는 용어가 있다는 것을 알게된 문제였다. 위상정렬 알고리즘에서 indegree는 배웠기 때문에 그냥 in 반대니까 outdegree라고 놓고 풀었는데, 실제로 있는 용어였다. (당연한가?)

 

 

오늘의 교훈) outdegree를 풀이에 활용하자