[백준 2252] 줄 세우기 (python)

2252번: 줄 세우기

---

위상 정렬을 이용한다. s -> e 순으로 와야할때 e의 진입차수는 1이라고 한다.

 

1. 수들의 관계를 저장할 ndict를 생성한다.
2. 진입 차수들을 저장하는 indegree를 생성한다.
3. 수들을 입력받으면서 ndict와 indegree를 update해준다.
4. 입력차수가 0인 수들을 queue에 넣는다.
5. queue에서 빼면서 해당 숫자에 연결되어 있는 숫자들의 입력 차수를 1빼준다.
6. 만약 입력차수가 0이 되었다면 queue에 넣어준다.

 

import sys
from collections import defaultdict, deque
input = sys.stdin.readline

N, M = map(int, input().split())
ndict = defaultdict(list)
indegree = [0]*(N+1)
for _ in range(M):
    s, e = map(int, input().split())
    ndict[s].append(e)
    indegree[e] += 1

result = []
queue = deque()
for i in range(1, N+1):
    if indegree[i] == 0:
        queue.append(i)

while queue:
    x = queue.popleft()
    result.append(x)

    for i in ndict[x]:
        indegree[i] -= 1
        if indegree[i] == 0:
            queue.append(i)

print(*result)