#3538. 驿站问询

题面

---

交互题。

给定一个包含 \(n\) 个点，\(m\) 条边的无向连通图 \(G=(V,E)\)。

最多 \(T\) 次查询，每次可以给定一个边集 \(E'\)，交互库将会返回 \(G'=(V,E\cap \overline{E'})\) 的连通性。

也即删去 \(E'\) 中所有边后（无论是否存在）图是否仍然连通。

试判定该图是否为二分图，若是则需报告其中一侧点集。

\[n\le 200, T\le 2000 \]

---

由于保证图连通，我们考虑先找出图的一颗生成树。

一个朴素的暴力想法是，对于每个点 \(i\)，我们取所有以 \(i\) 为端点的边构成的边集 \(V_i\)。

然后我们依次尝试删去每条边，直到删去某条边后图不联通，则该边为割边，必为生成树边。那么跳过这条边继续往后删。

对每个点进行一遍这个过程即可找到一颗生成树。

找出生成树之后即可判定是否为二分图，具体的，我们对树黑白染色。

要求为二分图即不存在同色边。我们删去所有异色非树边，然后对每条树边，询问额外删去这条边后是否连通。

若连通则说明存在同色边，即不为二分图。

---

考虑优化找树的过程。我们每次取 \(V_i\) 的任意一半 \(V'_i\)，询问删去 \(V'_i\) 后的连通性，若连通则说明割边（树边）不在其中。如此即可以 \(\log\) 的代价找到每一条树边。

这个技巧在 qoj14573 携春同行 中亦有应用。