숨겨진 그래프
시간 제한5초메모리 제한512 MB
모든 유도 부분 그래프에 차수가 k 이하인 정점이 있는 숨은 무향 그래프를 찾는다. 독립 집합 질의를 2nk+n번 이내로 사용하며, 독립 집합이 아니면 내부의 간선 하나를 알려준다.
문제
정점이 개인 단순 무향 그래프가 있다. 이 그래프는 다음 성질을 하나 더 만족한다.
- 어떤 유도 부분 그래프에서도 차수가 이하인 정점이 존재한다.
이 숨겨진 그래프를 찾아야 한다. 임의의 부분집합이 독립 집합인지 확인할 수 있다. 독립 집합이 아니라면, 그 집합 안에 양 끝점이 모두 들어 있는 간선 하나를 알려 준다.
상호작용 중에 그래프를 바꾸지 않으므로 그래프는 고정되어 있다고 가정해도 된다.
다만 유도 부분 그래프 안의 간선 중 어느 것을 보여 줄지는 우리가 정할 수 있다.
즉, 모든 테스트에서 그래프는 고정되어 있지만 인터랙터는 적응적이다.
번 이하의 질의로 그래프를 알아내야 한다.