BOJ 18195 정점 찾기

먼저 쿼리가 할 수 있는 일이 무엇인지 살펴보면, 두 개의 정점의 집합을 각각 연결되게 만든 다음 두 연결 요소가 숨겨진 간선에 의해 연결되는지를 확인할 수 있습니다.

각 정점 번호를 이진수로 나타내면 끝에서 $i$번째 비트가 0인 정점의 집합과 1인 정점의 집합은 서로 disjoint하며, 이렇게 쿼리를 넣은 결과가 1이면 $a \oplus b$의 $i$번째 비트가 1, 아니면 0임을 알 수 있습니다. 따라서 이러한 쿼리를 총 7번 진행하여 $a \oplus b$의 값을 알아낼 수 있습니다.

$a \oplus b$의 값을 알 때, $a$를 결정하면 $b$가 유일하게 결정되며, $(a, b)$와 $(b, a)$는 같은 간선이므로 가능한 간선은 최대 50개입니다. 이제 이분 탐색을 하여 6번의 쿼리로 이들 중 어느 간선인지 알아내면 됩니다.

먼저 $N$개의 정점을 절반으로 나눠서 쿼리를 합니다. 그 결과가 1이면 $a$와 $b$ 중 하나는 왼쪽 집합에, 다른 하나는 오른쪽 집합에 있습니다. 각각의 집합의 크기는 최대 50개이므로 각각 6번씩의 쿼리를 사용해 왼쪽 집합의 원소와 오른쪽 집합의 원소를 특정할 수 있습니다.

첫 번째 쿼리의 결과가 0이면, 두 정점이 모두 왼쪽 집합에 있거나 오른쪽 집합에 있지만, 어느 쪽인지는 모릅니다. 따라서 각각을 왼쪽과 오른쪽 절반으로 나눈 다음, 왼쪽끼리의 합집합과 오른쪽끼리의 합집합을 쿼리합니다. 두 번째 쿼리의 결과로 1이 나오면, 어느 모집합의 왼쪽과 오른쪽에 걸쳐 있었는지를 1번의 쿼리로 구할 수 있고, 나머지는 앞과 동일한 방법으로 두 집합에서 하나씩의 정점을 특정하면 됩니다.

두 번째 쿼리의 결과도 0이라면, 같은 방법으로 집합을 나누기를 반복합니다. 6번째 쿼리 이후에는 모든 집합의 크기가 2 이하이므로, 더 이상 집합 나누기를 할 필요 없이 어느 집합 내에 간선이 있는지를 확인하면 됩니다.