유명한 소 > 문제은행

본문 바로가기


알고리즘 자료구조2

1622 : 유명한 소

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 84 회    시도횟수: 394 회   



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


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) 순서쌍을 의미한다.



가장 유명한 소의 수를 출력한다.


[Copy]
3 3 
1 2 
2 1 
2 3
[Copy]
1


 강연결요소 PDF 




SCC, Tarjan, Kosaraju, poj2186

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.