U E D R , A S I H C RSS

3rdPCinCAUCSE/ProblemC

C 번 문제 : 구슬 찾기. 소스파일름 : ball.c or ball.cpp

모양은 같으나, 무게가 모두 다른 N개의 구슬 있다. N은 홀수며, 구슬에는 번호가 1,2, .... N으로 붙어있다. 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 아래와 같은 일을 하려 한다.
우리에게 주어진 것은 양팔 저울다. 한 쌍의 구슬을 골라서 양팔 저울의 양쪽에 하나씩 올려 보면 어느 쪽 무거운 가를 알 수 있다. 렇게 M개의 쌍을 골라서 각각 양팔 저울에 올려서 어느 것 무거운 가를 모두 알아냈다. 결과를 용하여 무게가 중간 될 가능성 전혀 없는 구슬들은 먼저 제외한다.
예를 들어, N=5 고, M=4 쌍의 구슬에 대해서 어느 쪽 무거운가를 알아낸 결과가 아래에 있다.

1. 구슬 2번 구슬 1번보다 무겁다.
2. 구슬 4번 구슬 3번보다 무겁다.
3. 구슬 5번 구슬 1번보다 무겁다.
4. 구슬 4번 구슬 2번보다 무겁다.

위와 같 네 개의 결과만을 알고 있으면, 무게가 중간인 구슬을 정확하게 찾을 수는 없지만, 1번 구슬과 4번 구슬은 무게가 중간인 구슬 절대 될 수 없다는 것은 확실히 알 수 있다. 1번 구슬보다 무거운 것 2,4,5번 구슬고, 4번보다 가벼운 것 1,2,3번다. 따라서 답은 2개다.
M개의 쌍에 대한 결과를 보고 무게가 중간인 구슬 될 수 없는 구슬의 개수를 구하는 프로그램을 작성하시오.

입력

입력은 표준 입력다. 입력의 첫줄에 테스트 케스의 개수를 나타내는 정수 T(10 하)가 주어진다. 다음 줄부터 T개의 테스트 케스가 주어진다. 각 테스트 케스의 첫 줄은 구슬의 개수를 나타내는 정수 N (1<=N<=99) 과 저울에 올려 본 쌍의 개수 M 이 주어진다. 그 다음 M개의 줄은 각 줄마다 두 개의 구슬 번호가 주어지는데, 앞 번호의 구슬이 뒤 번호의 구슬보다 무겁다는 것을 뜻한다.

출력

출력은 표준 출력다. 출력은 T줄로 뤄진다. 각 테스트 케스에 대해서 무게가 중간 절대로 될 수 없는 구슬의 수를 출력한다. T개의 테스트 케스를 모두 맞혀야 문제를 맞힌 것다.

입력의 예

~cpp 
2
5 4
2 1
4 3
5 1
4 2
3 1
1 2

입력의 예에 대한 출력

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:22:17
Processing time 0.0199 sec