[파이썬] 백준 18133 : 가톨릭대학교에 워터 슬라이드를?? (플레4)

[파이썬] 백준 18133 : 가톨릭대학교에 워터 슬라이드를?? (플레4)

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

---

풀이

방향성 생각

• SCC에서 진입차수가 0인 SCC개수를 출력하기
• 0-base인지 1-base인지 실수하지 말고, SCC 이후 len(SCC) 개수만큼 진입차수를 체크하는 리스트를 관리하기

 

---

파이썬

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+1)
P = [-1]*(N+1)
counter = [0]
stack = deque()
on_stack = [False]*(N+1)

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])

    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(1,N+1):
    if V[x]==-1:
        dfs(x)

GROUP = [-1]*(N+1)
for idx,scc in enumerate(SCC):
    for x in scc:
        GROUP[x] = idx

rank = [0]*len(SCC)
for x in range(1,N+1):
    for nx in G[x]:
        if GROUP[x] != GROUP[nx]:
            rank[GROUP[nx]] += 1
print(rank.count(0))

---

코멘트

• .