레이팅 미적용설명
\(1\)번부터 \(N\)번까지의 문제를 모두 풀려고 한다. "\(A\)번 문제는 \(B\)번 문제보다 먼저 푸는 것이 좋다"는 조건 \(M\)개가 주어진다.
다음 규칙을 지키며 문제를 푸는 순서를 구하여라.
- \(N\)개의 문제를 모두 푼다.
- 먼저 푸는 것이 좋은 문제가 있으면, 그 문제를 먼저 푼다.
- 가능하면 쉬운 문제(번호가 작은 문제)부터 푼다.
즉, 조건을 만족하는 순서 중 사전순으로 가장 앞서는 것을 구하면 된다.
제약
\(1 \le N \le 32\,000\), \(0 \le M \le 100\,000\).
입력 형식
첫째 줄에 \(N\)과 \(M\)이 주어진다. 다음 \(M\)개의 줄에 두 정수 \(A\ B\)가 주어진다 — \(A\)번을 \(B\)번보다 먼저 푸는 것이 좋다는 뜻이다. 항상 모든 문제를 풀 수 있는 경우(사이클이 없는 경우)만 주어진다.
출력 형식
문제를 풀 순서를 공백으로 구분해 한 줄에 출력한다.
예제 1
입력
4 2
4 2
3 1
출력
3 1 4 2
설명
\(3\)을 \(1\)보다, \(4\)를 \(2\)보다 먼저 풀어야 한다. 사전순 최소는 \(3\ 1\ 4\ 2\).
예제 2
입력
3 0
출력
1 2 3
설명
조건이 없으면 번호 순서대로 푼다.
문제 시리즈
힌트
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
힌트 1
로그인하고 잠금 해제 · 25 🪙
힌트 2
로그인하고 잠금 해제 · 50 🪙
문제 정보
riseoj 작성
출처 Original
태그