[BOJ] 2252번 : 줄 세우기

kimdozzi 2023. 8. 9. 21:05

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()