[Python]위상정렬 백준 2252

   문제

   https://www.acmicpc.net/problem/2252

위상정렬이란?

어떤 일을 하는 순서를 찾는 알고리즘이다.

아래 사이트를 참고하였다.

https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html

위상정렬은 다양한 답을 가질수 있으며 사이클이 포함되어있다면 위상정렬은 

불가능하다.

원리는 진입차수를 이용하여 진입차수가 0인 노드를 큐에 넣어주고 큐를빼면서 

연결된 노드의 진입차수를 갱신한다. 이때 진입차수가 0이된다면 해당노드를 큐에

 넣어주는 방식으로 큐가 빌때까지 반복해주면 된다.

만약 사이클이 있다면 진입차수가 0이하로 내려가게 된다.

import sys
from collections import deque
 
 
n,m=map(int,sys.stdin.readline().split())
tree=[[] for _ in range(n+1)]#트리
 
inDegree=[0 for _ in range(n+1)]#진입차수
q=deque()#사용할큐
result=[]#결과저장
 
 
for _ in range(m):
    s,e=map(int,sys.stdin.readline().split())
    tree[s].append(e)
    inDegree[e]+=1#진입차수
 
 
for i in range(1,n+1):
    if inDegree[i]==0:
        q.append(i)
 
while q:#큐가 빌때까지
    a=q.popleft()
    result.append(a)
    for t in tree[a]:
        inDegree[t]-=1#진입차수 갱신
        if inDegree[t]==0:#갱신된 진입차수가 0이라면 큐에 넣어준다.
            q.append(t)
 
print(*result)