USACO 2003 Fall  Popular Cows,  poj2186- 유명한 소 > 문제은행 : 정보올림피아드&알고리즘




1622 : 유명한 소

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
14 회   
시도횟수
59 회   

문제

무리에서 가장 유명해 지는 것은 모든 소들의 꿈이다.


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

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP