Мережа Дюлока#12972

Мережа Дюлока (Розбір)

Author:

Adrian Miclaus

Solved by:

First to solve:

[UAIC] Washbin

Let X \subseteq V. We denote by the number returned by the interactor. Let A, B \subseteq V be two sets of vertices such that A \cap B = \emptyset. If f(A) + f(B) \neq f(A \cup B), there are two cases:

Both cases represent the fact that and are connected. In fact, that also means that dist(x, y) \le 2 where is the distance between two vertices in the original graph.

Thus, we can start with A = \{1\} and B = \{2, 3, \dots, |V|\} and binary search the next vertex that can be added to such that we know that all vertices of are in the same connected component. Firstly, we can check that f(A) \ne 0, the graph is not connected otherwise. At each step of the binary search we divide the set into two sets B_1, B_2 such that B_1 has the first \frac{|B|}{2} elements, and B_2 the last |B| - \frac{|B|}{2}. If f(A) + f(B_1) \neq f(A \cup B_1), then we continue the search for the vertex to add to in B_1, otherwise in B_2. Then we know that the distance from the vertex we found to some vertex in is at most 2 and that means they are in the same connected component, so we can add that vertex to . The number of queries used is at most 2 \cdot |V| \log{|V|}.