문제 1030 · 중급 6

배포 순서 정하기

인증 제출 통계 · 5분마다 갱신 · 정답 비율 = 정답 제출 / 전체 제출
시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2000ms / 테스트 (언어별 보정은 아래 표)	메모리: 측정하지 않음(브라우저 채점)	0	0	0	0.00%

문제

마이크로서비스 N개(1번 ~ N번)를 새 서버에 하나씩 배포해야 한다. 'a 를 배포한 뒤에야 b 를 배포할 수 있다' 는 의존 관계가 M개 있다. 배포 담당자는 매번 '지금 배포할 수 있는 서비스(의존하는 서비스가 모두 배포된 서비스)' 중 번호가 가장 작은 것을 배포한다. 이 방식으로 정해지는 배포 순서를 구하라. 의존 관계가 순환해서 모든 서비스를 배포할 수 없으면 -1 을 출력한다.

입력

첫째 줄에 N 과 M 이 주어진다. (1 ≤ N ≤ 20,000, 0 ≤ M ≤ 40,000)

다음 M개 줄에 a 와 b 가 주어진다. a 를 b 보다 먼저 배포해야 한다는 뜻이다. (1 ≤ a, b ≤ N, a ≠ b) 같은 관계가 여러 번 나올 수 있다.

출력

배포 순서를 공백으로 구분해 한 줄에 출력한다. 불가능하면 -1 을 출력한다.

예제 입력 1

예제 출력 1

3 1 2 5 4

예제 입력 2

예제 출력 2

-1

힌트 펼치기

서비스마다 '아직 배포되지 않은 선행 서비스 수(진입 차수)' 를 세어 두고, 0 이 된 서비스를 후보로 둔다.
후보 중 번호가 가장 작은 것을 매번 꺼내야 하므로 후보를 우선순위 큐(최소 힙)에 넣자. 끝까지 N개를 못 꺼내면 순환이 있는 것이다.

풀이 작성

연습 채점은 공개 테스트로 실행합니다. 인증 제출은 코드를 봉인한 뒤 새 입력을 실행하고 서버에서 출력을 대조하며 코드와 판정을 저장합니다.

풀이를 제출하면 여기에서 결과를 확인할 수 있습니다.

연습 기록은 이 브라우저에 최근 50개를 저장합니다. 인증 기록은 내 제출에서 확인하세요.

이 브라우저의 제출 기록

언어별 제한

테스트 케이스마다 새 전역에서 실행하며 준비 시간은 제외합니다. 시간 초과된 출력은 검사하지 않습니다. 브라우저·기기 성능에 따라 실행 시간이 달라집니다.

언어	엔진(버전)	시간 제한	메모리
javascript	사용자 브라우저 JavaScript 엔진 (버전은 브라우저에 따라 다름)	2000ms / 테스트	측정하지 않음(브라우저 채점)
python	Pyodide 314.0.7 (CPython 3.14 WASM)	8000ms / 테스트	측정하지 않음(브라우저 채점)

문제

입력

출력