레이팅 미적용민준이는 컴퓨터공학과를 졸업하기 위해 전공 과목 \(N\)개(번호 \(1\)부터 \(N\))를 모두 이수해야 한다. 일부 과목 쌍에는 선수 관계가 있어서, "\(a\) \(b\)"로 주어지면 과목 \(a\)를 들은 다음 학기 이후에야 과목 \(b\)를 들을 수 있다.
교수진을 충분히 확보하여 한 학기에 들을 수 있는 과목 수에는 제한이 없다. 즉 선수 관계만 지켜진다면 서로 독립인 과목들은 같은 학기에 한꺼번에 들을 수 있다.
모든 과목을 이수하는 데 필요한 최소 학기 수를 구하여라. 선수 관계 그래프에는 사이클이 없음이 보장된다.
\(1 \le N \le 300{,}000\), \(0 \le M \le 500{,}000\). 같은 선수 관계가 두 번 이상 주어지지 않으며, 그래프에는 사이클이 없다.
첫째 줄에 과목 수 \(N\)과 선수 관계 수 \(M\)이 공백으로 주어진다. 이어 \(M\)개의 줄에 각각 두 정수 \(a\), \(b\)가 주어지며, 이는 과목 \(a\)가 과목 \(b\)의 선수 과목임을 뜻한다 (\(1 \le a, b \le N\), \(a \ne b\)).
모든 과목을 이수하는 데 필요한 최소 학기 수를 한 줄에 출력한다.
4 3
1 2
2 3
1 4
3가장 긴 선수 사슬은 \(1\to2\to3\) 으로 길이가 3이다. 과목 4는 \(1\) 다음 학기에 들을 수 있어 2학기에 끝난다. 따라서 최소 3학기가 필요하다.
5 0
1선수 관계가 전혀 없으므로 5과목을 모두 한 학기에 들을 수 있어 정답은 1이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original