백준 2252 줄세우기

위상정렬 문제

그래프를 인접리스트로 구현

 

indegree 배열 저장

자료구조 queue 사용

 

import queue

n, m =input().split()
n = int(n)
m = int(m)

adj = [[] for _ in range(n+1)]
indegree = [0] * (n+1)
Q = queue.Queue()

for _ in range(m):
    A, B = input().split()
    adj[int(A)].append(int(B))
    indegree[int(B)]+=1

for i in range(1,len(indegree)):
    if indegree[i] == 0:
        Q.put(i)

while not Q.empty():
    temp = Q.get()
    print(temp, end=' ')
    for i in range(len(adj[temp])):
        indegree[adj[temp][i]] -=1
        if indegree[adj[temp][i]] ==0:
            Q.put(adj[temp][i])