[BOJ] 24526 - 전화 돌리기 (Python)

 

 

아이디어

 

전화를 넘겨 받을 수 있는 부원을 선행으로 위상 정렬하여 진입 차수가 0이 되는 부원의 수를 구한다.

 

 

풀이

 

진입 차수가 0이 되지 않는 부원들은 사이클이 발생하는 구간에 존재한다.

 

import sys

input = sys.stdin.readline

def solution():
    N, M = map(int, input().split())
    graph = [dict() for _ in range(N+1)]
    D = [0]*(N+1)
    for _ in range(M):
        U, V = map(int, input().split())
        if graph[V].get(U, 0) == 0:
            graph[V][U] = 1
            D[U] += 1
    stack = []
    for i in range(1, N+1):
        if D[i] == 0:
            stack.append(i)
    while stack:
        v = stack.pop()
        for u in graph[v].keys():
            D[u] -= 1
            if D[u] == 0:
                stack.append(u)
    print(D.count(0)-1)

solution()