1622 : 유명한 소
- 제한시간
- 1000 ms
- 메모리제한
- 64 MB
- 해결횟수
- 20 회
- 시도횟수
- 71 회
문제
무리에서 가장 유명해 지는 것은 모든 소들의 꿈이다.
N(1≤N≤10,000) 마리의 소로 구성된 무리에서, 당신은 M(1≤M≤50,000)개의 관계를 입력받는다.
각 관계는 (A, B) 순서쌍 형태로 A가 생각하기에 B가 유명하다는 정보이다.
유명함은 "transitive"하다.
즉, A가 생각하기에 B가 유명하고, B가 생각하기에 C가 유명하면, A가 생각하기에도 C가 유명한 것이다.
이는 (A, C) 순서쌍이 입력되지 않는다고 하더라도 A는 자연스럽게 C가 유명하다고 생각한다.
당신이 해야 할 일은 소 무리에서 가장 유명한 소들의 수를 출력하는 것이다.
가장 유명한 소는 다른 모든 소들이 유명하다고 생각하는 소를 말한다.
입력형식
첫 줄에 두 정수 N과 M을 입력받는다. 둘째 줄부터 M줄에 걸쳐 매 줄마다 두 정수 A와 B가 입력된다. 이는 (A, B) 순서쌍을 의미한다.
출력형식
가장 유명한 소의 수를 출력한다.
입력 예3 3 1 2 2 1 2 3 |
출력 예1 |
Hint!
SCC, Tarjan, Kosaraju