[강한 연결 요소/파이썬] 백준 2150번 : Strongly Connected Component / 플래5

https://www.acmicpc.net/problem/2150

2150번: Strongly Connected Component

import collections
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
v, e = map(int, input().split())

graph = collections.defaultdict(list)
for _ in range(e):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)  # convert node number to node index

d = [-1 for _ in range(v)]
stack = []
on_stack = [False for _ in range(v)]
scc_lst = []
id = 0

def dfs(cur):
    global id
    id += 1
    d[cur] = id
    stack.append(cur)
    on_stack[cur] = True

    parent = d[cur]
    for next in graph[cur]:
        if d[next] == -1:  # 방문 이력이 없는 노드
            parent = min(parent, dfs(next))
        elif on_stack[next]:  # 방문 체크는 되어있지만 아직 처리 완료 x
            parent = min(parent, d[next])

    # scc result
    if parent == d[cur]:  # 자신과 부모가 동일
        scc = []
        while True:
            node = stack.pop()
            on_stack[node] = False
            scc.append(node+1)  # 인덱스에 1을 더해주어야 노드 번호가 됨
            if cur == node:
                break
        scc_lst.append(sorted(scc))
    return parent

for i in range(v):
    if d[i] == -1:  # 방문 이력이 없는 노드
        dfs(i)

scc_lst.sort()
print(len(scc_lst))
for i in range(len(scc_lst)):
    print(*sorted(scc_lst[i]), end=' ')
    print(-1)

사실 아직 플래티넘 난이도 문제를 자유자재로 풀 수준은 안되지만,

강한연결요소 알고리즘을 배운김에 풀어봤더니 이 문제는 SCC 그 자체라 쉽게 풀렸다.

 

 

++ 약간 더 수정

dfs를 사알짝 더 간결하게

import collections
import sys

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

v, e = map(int, input().split())

graph = collections.defaultdict(list)
for _ in range(e):
    a, b = map(int, input().split())
    graph[a - 1].append(b - 1)  # convert node number to node index

d = [-1 for _ in range(v)]
stack = []
on_stack = [False for _ in range(v)]
scc_lst = []
id = 0


def dfs(cur):
    global id
    cur_id = id
    id += 1

    d[cur] = cur_id
    stack.append(cur)
    on_stack[cur] = True

    for next in graph[cur]:
        if d[next] == -1:  # 방문 이력이 없는 노드
            dfs(next)
            d[cur] = min(d[cur], d[next])

        elif on_stack[next]:  # 방문 체크는 되어있지만 아직 처리 완료 x
            d[cur] = min(d[cur], d[next])

    # scc result
    if d[cur] == cur_id:  # cur는 현재 scc의 부모 노드
        scc = []
        while True:
            node = stack.pop()
            on_stack[node] = False
            scc.append(node + 1)  # 인덱스에 1을 더해주어야 노드 번호가 됨
            if cur == node:
                break
        scc_lst.append(sorted(scc))


for i in range(v):
    if d[i] == -1:
        dfs(i)

scc_lst.sort()

print(len(scc_lst))
for i in range(len(scc_lst)):
    print(*sorted(scc_lst[i]), end=' ')
    print(-1)