[파이썬] 백준 2150 : Strongly Connected Component (플레5)

[파이썬] 백준 2150 : Strongly Connected Component (플레5)

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

---

풀이

방향성 생각

• 타잔 알고리즘. 그래프의 사이클 탐색하기

 

전체코드

import sys
sys.setrecursionlimit(10**6)

input = lambda : sys.stdin.readline().rstrip()

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

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

cnt = 0
V = [-1]*(N+1)
P = [-1]*(N+1)
on_stack = [False]*(N+1)
stack = []
SCC = []

def dfs(x):

    global cnt

    # 1. 방문 체크 / 카운터 관리 / 스택 관리
    V[x] = cnt
    P[x] = cnt
    cnt += 1
    stack.append(x)
    on_stack[x] = True

    # 2. 스택 관리
    for nx in G[x]:
        if V[nx] == -1: # 미방문 노드
            dfs(nx)
            P[x] = min(P[x],P[nx])
        elif on_stack[nx]: # SCC에 할당되지 않은 노드에 최소 번호 부여하기 (스택에 없으면 이미 scc에 할당)
            P[x] = min(P[x],V[nx])

    # 위상정렬 + SCC 진행 / 위상정렬이 필요 없으면 P 배열만 순회하며 된다.
    if V[x] == P[x]:
        temp = []
        while True:
            w = stack.pop()
            on_stack[w] = False
            temp.append(w)
            if w == x:
                break
        SCC.append(temp)

# 타잔알고리즘 실행
for x in range(1,N):
    if V[x] == -1:
        dfs(x)

# 결과 출력
SCC.sort(key= lambda scc : min(scc))
print(len(SCC))
for scc in SCC:
    print(*sorted(scc), -1)

코멘트

• 위상정렬 공부하면서 타잔 알고리즘 공부한 김에 풀이.
• 타잔 알고리즘을 사용하면, 위상정렬의 역순으로 SCC를 얻을 수 있다.
• 그리고 global로 보통 처리를 했는데 레퍼런스 타입인 리스트로 [int] 이렇게 숫자 하나만 넣고 global이나 nonlocal없이 재귀호출된 값을 사용할 수 있다.
• 전체적인 순서 타잔 알고리즘 순서
  1. dfs를 진행하면 방문체크 (V랑 P에) + 카운터 관리 + 스택관리
  2. 탐색 진행 : 미방문 노드 / SCC 미할당 노드 관리
  3. 위상정렬 + SCC 추출