题解：CF1033E Hidden Bipartite Graph

· · 题解

题意：

交互。

有一个 n 个点 m 条边的无向简单联通图，你不知道除了 n 外的任何其他信息，每次询问选择一个点集 S，交互库返回有多少条边的两端都在 S 内，你需要在至多 2 \times 10^4 次询问内判定图是否为二分图。如果是，你需要求出黑白染色结果，若不是，你需要求出图的一个奇环。交互库可能自适应。

解法： 不可能将整个图的形态求出。 但是对于图上的这类问题，常见做法是能不能考虑 DFS 生成树。 事实上，我们可以在 $O(n \log n)$ 次询问内求出图的一棵 DFS 生成树。具体地，维护目前未被访问过的点集，每次往下 DFS 时二分找到集合中第一个和其有边的点即可。 然后对树进行黑白染色，考虑询问黑白内部是否有边即可判定是否为二分图。若不是，容易直接求出同色的一条边，在树上选这条边的端点对应路径就找到了一个奇环。 范围很松，我的实现最坏询问次数不超过 $12000$。 [Submission Link.](https://codeforces.com/problemset/submission/1033/290510157)