백준 2150 - Strongly Connected Component (Python)

되게 생소한 개념이라 찾아가며 풀었습니다.
자세한 내용은 코사라주 알고리즘, 타잔 알고리즘을 찾아보면 됩니다.

Kosaraju algorithm

import sys
sys.setrecursionlimit(10 ** 6)

v, e = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(v + 1)]
reverse_graph = [[] for _ in range(v + 1)]
for _ in range(e):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    reverse_graph[b].append(a)

def dfs(node, visited, stack):
    visited[node] = 1
    for ne in graph[node]:
        if visited[ne] == 0:
            dfs(ne, visited, stack)
    stack.append(node)

def reverse_dfs(node, visited, stack):
    visited[node] = 1
    stack.append(node)
    for ne in reverse_graph[node]:
        if visited[ne] == 0:
            reverse_dfs(ne, visited, stack)

stack = []
visited = [0] * (v + 1)

for i in range(1, v + 1):
    if visited[i] == 0:
        dfs(i, visited, stack)
        
visited = [0] * (v + 1)
result = []

while stack:
    ssc = []
    node = stack.pop()
    if visited[node] == 0:
        reverse_dfs(node, visited, ssc)
        result.append(sorted(ssc))

print(len(result))
results = sorted(result)
for i in results:
    print(*i, -1)

Tarjan algorithm

import sys
sys.setrecursionlimit(10 ** 6)

v, e = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(v + 1)]
for _ in range(e):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)

stack = []
low = [-1] * (v + 1)
ids = [-1] * (v + 1)
visited = [0] * (v + 1)
idid = 0
result = []

def dfs(x, low, ids, visited, stack):
    global idid
    ids[x] = idid
    low[x] = idid
    idid += 1
    visited[x] = 1
    stack.append(x)

    for ne in graph[x]:
        if ids[ne] == -1:
            dfs(ne, low, ids, visited, stack)
            low[x] = min(low[x], low[ne])
        elif visited[ne] == 1:
            low[x] = min(low[x], ids[ne])

    w = -1
    scc = []
    if low[x] == ids[x]:
        while w != x:
            w = stack.pop()
            scc.append(w)
            visited[w] = -1
        result.append(sorted(scc))

for i in range(1, v + 1):
    if ids[i] == -1:
        dfs(i, low, ids, visited, stack)
print(len(result))
for i in sorted(result):
    print(*i, -1)