네트워크 감시

시간 제한1초메모리 제한128 MB

요약
여러 그래프가 주어질 때 각 그래프에서 크기 10 이하의 정점 커버가 존재하는지 판별합니다.
난이도

보통10점 중 7점

유형
그래프, 백트래킹, 완전 탐색
정답자
아직 제출이 없습니다

문제

어떤 기관이 컴퓨터 네트워크의 모든 직접 통신선을 감시하려고 한다. 감시 소프트웨어는 최대 10대의 호스트에만 설치할 수 있다. 소프트웨어가 제대로 동작하려면 모든 직접 통신선 A-B에 대해 두 끝점 A 또는 B 중 적어도 하나가 감시 대상이어야 한다.

각 네트워크에 대해 최대 10개의 호스트를 골라 모든 통신선을 덮을 수 있는지 판단하라.

입력

입력은 여러 네트워크 시나리오로 이루어진다. 각 시나리오는 다음 형식이다.

  • 첫 줄에는 호스트 수 n이 주어진다. (10 <= n <= 2500)
  • 이어서 호스트마다 한 줄씩, 총 n개의 줄이 주어진다. 호스트의 이름은 0, 1, ..., n-1이다. 첫 번째 줄은 호스트 0의 이웃, 두 번째 줄은 호스트 1의 이웃을 나타내며, 마지막 줄은 호스트 n-1의 이웃을 나타낸다.
  • 각 줄은 정수 d로 시작한다. (1 <= d < n) 이는 해당 호스트와 직접 통신선으로 연결된 이웃의 수이다. 뒤이어 이웃 호스트의 번호 d개가 공백으로 구분되어 오름차순으로 주어진다. 모든 이웃 번호는 해당 호스트 자신을 제외한 0 이상 n-1 이하의 유효한 번호이다.

마지막 줄에는 0만 주어진다. 이 줄은 처리하지 않는다.

출력

각 네트워크마다 한 줄을 출력한다. 시나리오 번호는 1부터 시작한다.

출력 형식은 Network n: yes 또는 Network n: no이다. 여기서 n은 시나리오 번호이다. 최대 10개의 호스트를 골라 모든 직접 통신선을 감시할 수 있으면 yes, 그렇지 않으면 no를 출력한다.

예제1

  1. 예제 1

    입력
    11
5 1 3 5 8 10
5 0 2 4 6 9
5 1 3 5 6 10
4 0 2 4 6
4 1 3 5 7
5 0 2 4 6 8
6 1 2 3 5 7 9
4 4 6 8 10
4 0 5 7 9
4 1 6 8 10
4 0 2 7 9
11
10 1 2 3 4 5 6 7 8 9 10
10 0 2 3 4 5 6 7 8 9 10
10 0 1 3 4 5 6 7 8 9 10
10 0 1 2 4 5 6 7 8 9 10
10 0 1 2 3 5 6 7 8 9 10
10 0 1 2 3 4 6 7 8 9 10
10 0 1 2 3 4 5 7 8 9 10
10 0 1 2 3 4 5 6 8 9 10
10 0 1 2 3 4 5 6 7 9 10
10 0 1 2 3 4 5 6 7 8 10
10 0 1 2 3 4 5 6 7 8 9
12
11 1 2 3 4 5 6 7 8 9 10 11
11 0 2 3 4 5 6 7 8 9 10 11
11 0 1 3 4 5 6 7 8 9 10 11
11 0 1 2 4 5 6 7 8 9 10 11
11 0 1 2 3 5 6 7 8 9 10 11
11 0 1 2 3 4 6 7 8 9 10 11
11 0 1 2 3 4 5 7 8 9 10 11
11 0 1 2 3 4 5 6 8 9 10 11
11 0 1 2 3 4 5 6 7 9 10 11
11 0 1 2 3 4 5 6 7 8 10 11
11 0 1 2 3 4 5 6 7 8 9 11
11 0 1 2 3 4 5 6 7 8 9 10
0
    예상 출력
    Network 1: yes
Network 2: yes
Network 3: no