[백준 2150번] Strongly Connected Component (Python3)

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

def DFS(now):
  global num
  nownum = num
  visited[now] = num
  stack.append(now)
  for next in graph[now]:
    if not visited[next]:
      num += 1
      DFS(next)
    visited[now] = min(visited[now],visited[next])
  if visited[now] == nownum:
    scc.append([])
    while 1:
      x = stack.pop()
      visited[x] = 1e6
      scc[-1].append(x)
      if x==now:
        break

N,M = map(int,input().split())

graph = [[] for i in range(N+1)]
for i in range(M):
  a,b = map(int,input().split())
  graph[a].append(b)

visited = [0]*(N+1)
scc = []; stack = []
for i in range(1,N+1):
  if not visited[i]:
    num = 1
    DFS(i)
scc = sorted([*map(sorted,scc)])
print(len(scc))
for s in scc:
  print(*s,-1)

SCC 기본문제이다.

기본문제 플래티넘답게 구현이 꽤 까다로웠다. 코드를 베끼기보다는 원리노트를 보고 직접 구현하려고 시도했는데, 예상치 못한 반례들이 꽤 많았다.

원리는 https://yjg-lab.tistory.com/188 를 참조하였다.

 

내가 한 실수를 정리하면,

1. DFS에서 각 노드의 탐사번호를 노드의 깊이로 해선 안된다.

2. 한번의 DFS로 모두 탐사할 수 있는것이 아니다. 방문하지 않은 모든 노드에 대해서 DFS를 해주어야한다.

3. 2번에서 서로 다른 scc끼리 간섭될 수 있으므로 이미 scc에 넣은 노드는 따로 처리해주어야한다.

 

 

오늘의 교훈) SCC를 활용해서 다양한 문제를 해결해보자