全体の辺数と連結成分数が分かれば閉路判定を行うことができます。深さ優先探索によって連結成分を特定することを考えると、ある頂点と結ばれているまだ訪れたことのない頂点を効率的に見つけることができればよいです。

頂点集合 \(S\) に対するクエリの答えを \(\mathrm{query}(S)\) とします。頂点 \(u\) と頂点集合 \(T\) に対し、\(u\) と \(T\) に属する頂点を結ぶ辺の本数を \(f(u, T)\) とおくと、\(f(u, T) = \mathrm{query}(T \cup \{u\}) - \mathrm{query}(T)\) となります。

まだ訪れたことのない頂点が \(A_1, \dots, A_n\) であるとします。\(f(u, \{A_1, \dots, A_n\}) > 0\) であるとき、以下のようにして \(u\) と結ばれている頂点を一つ求めることができます。

• 頂点の候補が \(2\) 個以上ある間、次の処理を行う。

  • \(m = \lfloor \frac{n}{2} \rfloor\) とする。\(f(u, \{A_1, \dots, A_m\}) > 0\) ならば \(A_1, \dots, A_m\) を、そうでないなら \(A_{m+1}, \dots, A_n\) を新たな候補とする。

\(2 \lceil \log_2 N \rceil\) 回の質問で一つの辺を特定することができるので、全体で \(2N \log_2N + 2N\) 回や \(2N \log_2N + N\) 回程度の質問回数でこの問題を解くことができました。

実装例 (C++)