[파이썬] 백준 15783 : 세진 바이러스 (플레4)

[파이썬] 백준 15783 : 세진 바이러스 (플레4)

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

---

풀이

방향성 생각

• 타잔 알고리즘에서 구한 SCC 결과에서 진입차수가 0인 scc를 구해주면 된다.
• 0-base인지 1-base인지 확인해주기

 

---

전체코드

from collections import deque
import sys
sys.setrecursionlimit(10**6)

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

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)

# 방문, 그룹관리 / 카운터 관리 / 스택 관리
V = [-1]*N
P = [-1]*N
counter = [0]
stack = deque()
on_stack = [False]*N

SCC = []
def dfs(x):

    # 방문처리, 카운터 증가, 스택 처리
    V[x] = counter[0]
    P[x] = counter[0]
    counter[0] += 1
    stack.append(x)
    on_stack[x] = True

    # 인접 노드 탐색
    for nx in G[x]:
        if V[nx] == -1:
            dfs(nx)
            P[x] = min(P[x],P[nx])
        elif on_stack[nx]:
            P[x] = min(P[x],V[nx])

    # SCC 추출하기기
    if V[x] == P[x]:
        scc = []
        while True:
            w = stack.pop()
            on_stack[w] = False
            scc.append(w)
            if w==x:
                break
        SCC.append(scc)

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

# 그룹별로 묶기
GROUP = [-1]*N
for idx,scc in enumerate(SCC):
    for x in scc:
        GROUP[x] = idx

# 압축 그래프에서 진입차수 계산해주기
rank = [0]*len(SCC)
for x in range(N):
    for nx in G[x]:
        if GROUP[x] != GROUP[nx]:
            rank[GROUP[nx]] += 1

# 진입차수가 0인 경우 처리해주기.
print(rank.count(0))

코멘트

• 타잔 알고리즘 SCC + 위상정렬까지는 풀이 완료.
• 2-SAT 공부하기