[백준 파이썬] 2252번 줄 세우기

2252번 줄 세우기

 

풀이

 학생들의 키 비교 정보로 유향 그래프를 생성합니다. 그리고 위상정렬 알고리즘으로 풀었습니다.

import collections

v, e = map(int, input().split())
in_degree = [0] * (v+1)
graph = [[] for i in range(v+1)]

for _ in range(e):
    a, b = map(int,input().split())
    graph[a].append(b)
    in_degree[b] += 1
    
result = []
q = collections.deque()

for i in range(1, v+1):
    if in_degree[i] == 0:
        q.append(i)
        
while q:
    node = q.popleft()
    result.append(node)
    
    for i in graph[node]:
        in_degree[i] -= 1
        if in_degree[i] == 0:
            q.append(i)

for i in result:
    print(i, end=' ')