https://www.acmicpc.net/problem/2252
2252번: 줄 세우기
첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의
www.acmicpc.net
알고리즘 : 위상 정렬
import itertools
import sys, heapq
si = sys.stdin.readline
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from math import factorial,sqrt
from itertools import permutations, combinations, accumulate
mn, mx = float('inf'), float('-inf')
def topology_sort() :
res=[]
q = deque([])
for i in range(1,n+1) :
if indegree[i] == 0 :
q.append(i)
while q :
cur = q.popleft()
res.append(cur)
for i in graph[cur] :
indegree[i] -= 1
if indegree[i] == 0 :
q.append(i)
for i in res :
print(i, end=' ')
n,m=map(int,si().split())
indegree=[0 for _ in range(n+1)]
graph=[[] for _ in range(n+1)]
for _ in range(m) :
a,b=map(int,si().split())
graph[a].append(b)
indegree[b] += 1
topology_sort()