경로강화 > 문제은행



실전대비 Level3

1209 : 경로강화

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



N개의 도시가 있고, 각 도시는 1번부터 N번까지 번호가 붙어있다.

인접해 있는 도시끼리는 다리로 연결되어있다. 

다리가 연결되어 있는 도시에서 도시로는 이동 가능하며, 여러 개의 다리를 거쳐서 다른 곳으로 가는 것 역시 허용된다.

허나 다리가 끊어지면 어떤 도시에서 어떤 도시로 가는 경로가 존재하지 않는 경우가 발생하게 되는데, 

추가적인 다리를 연결하여 어떤 다리가 하나 끊어져도 

모든 도시간의 경로가 존재하기 위한 최소 추가해야할 다리의 개수를 알아내는 프로그램을 작성하라.




첫 번째 줄에는 도시의 개수를 나타내는 정수 N(1≤N≤1,000)과, 이어진 다리의 개수 B(N-1≤B≤10,000)이 주어진다.

그 다음 줄부터는 B개의 다리의 정보가 주어지는데, 두 개의 정수로 지어지며, 이는 해당 번호를 가진 두 도시 사이에는 다리가 존재한다는 것이다.




다리 하나가 끊어져도 모든 도시간의 경로가 존재하기 위해 추가해야할 최소의 다리의 개수를 출력한다.



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






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.