시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 229 | 43 | 30 | 26.087% |
간선에 방향성이 있는 트리(사이클이 없는 연결 그래프)가 주어진다. 트리에 특별 경로를 가능한 적게 추가해서, 모든 노드에서 다른 노드로 이동할 수 있게 하는 프로그램을 작성하시오.
특별 경로는 아래와 같은 규칙을 지켜야 한다.
아래 트리를 살펴보자. 검정 간선은 원래 트리의 간선을 나타내고, 동그라미는 노드를 나타낸다. 그 다음, 두 개의 특별 경로 2-1-0(초록색)과 3-1(파란색)를 추가한다. 3-1대신에 3-1-0을 추가해도 된다. 하지만, 1-3이나 0-1-2는 규칙 2 때문에 추가할 수 없고, 0-2와 2-3-0은 규칙 1 때문에 추가할 수 없다.
첫째 줄에 테스트 케이스의 개수 T(≤30)이 주어진다.
각 테스트 케이스의 첫째 줄에는 노드의 수 N이 주어진다. (2 ≤ N ≤ 20000) 노드는 0번부터 N-1번까지 번호가 매겨져 있다. 다음 N-1줄에는 간선 정보를 나타내는 u와 v가 주어진다. (0 ≤ u, v < N, u ≠ v) u에서 v로 향하는 간선이라는 뜻이다.
각 테스트 케이스에 대해서, 케이스 번호와 모든 노드가 서로 연결될 수 있게 하기 위해서 추가해야 하는 특별 경로 개수의 최솟값을 출력한다.
2 4 0 1 1 2 1 3 5 0 1 1 2 1 3 0 4
Case 1: 2 Case 2: 3
ICPC > Regionals > Asia Pacific > Thailand > 2011 ACM-ICPC Asia Phuket Regional Programming Contest I번