jams > 문제은행



실전대비 Level1

1079 : jams

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



농장에서 소들의 마리수가 증가함에 따라 외양간으로 향하는 소의 도로에 심각한 혼잡이 발생하였다.

농부 창호는 우유를 짜는 시간대의 교통체증을 완화시키기 위해 병목지점을 찾는 방법을 만들어 보고자 했다.

 

목장은 M(1≤M≤50,000)개의 일방통행 도로를 가진 네트워크를 포함하며, 

각각의 도로는 1~N까지 번호가 매겨진 N(1≤N≤5,000)개의 교차점 중 서로 다른 두 개의 교차점을 연결한다.

외양간은 N번 교차점에 있다.

 

각각의 도로는 한 교차점에서 그 교차점보다 표기숫자가 높은 교차지점으로 연결 된다.

(예컨데 3->4연결은 있으나 4->3연결은 있을 수 없다.) 

따라서 도로에는 사이클이 없으며 모든 길들은 외양간에 이어지게 된다.

 

한 쌍의 교차점들은 한 개 이상의 도로로 연결 될 수 있다.
우유를 짜는 혼잡한 시간대에, 소들은 그들 각각의 풀을 뜯는 장소에서 시작하여 외양간을 향해 간다.
풀 뜯는 장소들은 교차점 중에서 그 어떤 도로도 해당 교차점을 향해서 들어가지 않는 교차점들이다.

 

창호를 돕기 위하여 다음과 같은 작업을 해보자.

소들이 목초지로부터 외양간으로 이동하는 경로들중 가장 많은 경로에 포함되는 도로를 찾아

이 도로를 지나는 경로의 수를 구하는 프로그램을 작성하자.

 

입력예 1번에 대한 설명을 하자면 다음과 같다.

목초지로부터 외양간에 이르는 경로는 아래와 같다.

1 3 4 6 7 

1 3 5 6 7 
2 3 4 6 7 

2 3 5 6 7

이 중에 가장 많이 포함된 도로는 6번 7번을 잇는 도로이고 모두 4개의 경로에 포함된다.

 

정답은 2^31 -1 이하이다.


첫 번째 줄에는 공백을 사이에 두고 N과 M이 주어진다. 두 번째 줄부터 M+1 번째 줄엔 공백을 간격으로 도로가 연결하는 두 교차점의 번호가 주어진다.



임의의 한 도로를 지나는 최대의 길 숫자를 출력한다.


7 7
1 3
3 4
3 5
4 6
2 3
5 6
6 7
4






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.