[snippet] tarjan.py

백준 2150번. Strongly Connected Component에 대한 풀이를 Tarjan's Algorithm의 스니펫 느낌으로 작성.

• 강한 연결 요소(SCC; Strongly Connected Component)를 구할 때 사용.
• latest & order 변수를 굳이 도입해야 하는 이유
  • parent를 통일할 기준이 필요한 상황이다.
  • Union-Find는 무방향이라 그냥 둘 중에 노드 번호 작은거 하면 됐지만,
    SCC는 단방향이라 나중에 사이클임을 확인했을 때가 되서야 parent 확정 가능

1. 뒤늦게 방문하여 사이클을 만드는 노드는 방문당하는 노드 번호(x)로 parent를 통일해야 하는 것이 타당하며,
2. 이를 위해서는 노드 번호가 아니라 방문 순서를 기준으로 parent를 통일해야 한다.
3. 이후, 재귀 스택이 풀리면서 해당 사이클의 원소는 모두 parent를 x로 통일한다.

import sys
input = lambda: sys.stdin.readline().rstrip()
miis = lambda: map(int, input().split())
sys.setrecursionlimit(10**5)

V, E = miis()
graph = [[] for _ in range(V+1)]
for _ in range(E):
    A, B = miis()
    graph[A].append(B)

latest = 1
order = [0] * (V+1) # 방문 순서
finished = [False] * (V+1)
stack = []
SCC = []

##########################

def get_scc(idx):
    ret = []
    t = 0
    while t != idx:
        t = stack.pop()
        ret.append(t)
        finished[t] = True
    return ret

def dfs(i):
    global latest
    
    order[i] = latest; latest += 1
    stack.append(i)
    parent = order[i]
    for j in graph[i]:
        if order[j] and finished[j]:
            continue
        parent = min(parent, dfs(j) if not order[j] else order[j])
        # order[j]가 택해지는 상황은, 오로지 사이클이 생기는 그 순간밖에 없음
    
    if parent == order[i]:
        SCC.append(get_scc(i))
    return parent

for i in range(1, V+1):
    if not order[i]:
        dfs(i)

##########################
        
for i in range(len(SCC)):
    SCC[i].sort()
SCC.sort(key=lambda x: x[0])

print(len(SCC))
for scc in SCC:
    print(*scc, -1)