백준 - 줄 세우기 (2252)

 

위상 정렬을 통해 풀 수 있다.

오랜만에 써보는 거라 다시 복습했다.

일단 키를 재는 문제이기에 그래프에 사이클이 없다고 판단했다.

 

graph에 이동 경로를 넣어준다.

목적지가 b이기에 indegree 리스트에 진입차수를 올려준다.

 

진입차수가 0인것을 모두 queue에다가 삽입하고 시작

큐에서 하나씩 팝해가면서 진입차수를 빼주고 

진입차수가 0이되면 큐에 삽입

 

무한반복

 

 

from collections import deque
def topology_sort():
    answer = []
    q = deque()
    for i in range(1, v+1):
        if indegree[i] == 0:
            q.append(i)
    while q:
        cur = q.popleft()
        answer.append(cur)

        for i in graph[cur]: # 진입차수 빼주기
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)
    return answer
# 노드와 간선의 개수
v, e = map(int, input().split())
indegree = [0] * (v+1)
graph = [[] for i in range(v+1)]

for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1

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