시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 370 | 172 | 139 | 49.466% |
울산광역시는 큰 도시라 고도로 발달했으면서도 복잡한 교통 체계를 가지고 있다. 울산광역시의 교통 체계는 정류장(정점)과 그 정류장을 잇는 도로(간선)들로 나타낼 수 있다. 정류장과 도로를 모은 그래프는 순환하는 경로가 발생하지 않는 형태이며, 서로 다른 두 정류장을 잇는 경로는 항상 만들 수 있다. 즉, 트리 모양이다.
이번에 교통과에 취직한 윤표는 버스 노선이 너무 많다고 생각해 이를 정리하기로 마음먹었다. 과감하게도, 윤표는 기존에 있던 버스 노선들을 모두 없애 버리고 버스 노선들을 새롭게 구성하려고 한다. 각각의 버스 노선은 다음과 같이 정의할 수 있다.
윤표는 모든 도로에 적어도 하나 이상의 버스 노선이 지나가도록 버스 노선을 구성하고 싶다. (도로에서 노선이 지나가는 방향은 어떤 방향도 상관없다.) 또한, 윤표는 버스 노선의 개수가 최소화되기를 원한다. 윤표를 도와, 모든 도로에 적어도 하나 이상의 버스 노선이 지나가도록 할 때 버스 노선의 최소 개수를 구하는 프로그램을 작성하자.
첫 번째 줄에 정류장의 수 N(2 ≤ N ≤ 200,000)가 주어지며 정류장은 0부터 N-1까지 고유한 번호를 가진다.
두 번째 줄부터 N번째 줄까지 도로로 연결된 두 정류장 쌍이 주어진다. 같은 도로가 여러 번 주어지지 않는다.
버스 노선을 정리했을 때 노선의 최소 개수를 출력한다.
9 1 2 6 7 8 2 4 5 3 4 2 6 0 3 5 8
2
University > UNIST > 제 1회 UNIST 알고리즘 프로그래밍 경시대회 Uni-CODE E번