交互题。
有一张连通图。你不知道它的形态。你可以做出一些询问，每次询问给出一些点对，会得知当这些点对中的边都断掉之后图还是否联通。任务是判断该图是否是二分图，如果是则返回其中一部的所有点。
，询问次数2000。
很妙。考虑题目的性质，图是联通的，且我们每次可以得知与连通性相关的信息。要向这方面的模型想，则容易想到生成树具有这样的性质：
连通图一定有生成树，且生成树断掉任意边都不连通，且树是二分图。
考虑找出这张图的生成树。
容易想到对每条边判断它是否在生成树内，即试图断掉每条边，如果仍联通就断掉，否则就把它加入生成树。这样的询问次数是 的，无法通过。
考虑加速判断过程。因为我们不断断边的过程中联通性一定是单调的，所以我们可以二分，二分 次即可找出生成树。优化到了 。算一下仍无法通过。
尝试去掉2的常数。二分肯定是跑不了了，发现有2的常数是因为我们在对边二分。对点二分可能就可以去掉2的常数了。
思考一下之后有这样的做法：对每个点 尝试断掉它与其他点之间的边，用二分优化。若找到了断掉会影响连通性的边则加入生成树，继续二分，否则断掉该点与其他点之间不是生成树上边的边之后换点继续上述过程。
但是这个做法仍然会有2的常数。因为对每个点都会有一次失败的二分无法找到生成树上的边，就做了 次二分。
算法似乎陷入了瓶颈。我们考虑为什么会这样。我们问得太多肯定是因为我们知道的太多了！233。我们知道什么？我们会知道一棵生成树。我们真的有必要知道这棵生成树么？？我们不是只需要知道每个点是属于哪一部，或者判出有奇环就好了么？所以我们其实没有必要知道边到底是谁跟谁连的！
整理一下思路：我们要对点二分，不允许有失败的二分，要知道点所属的部，不需要知道具体边是怎么连的。
算法渐渐清晰起来了。
我们设已经确定了所属部的点的集合为 ，剩下未知的点为 。
我们尝试断掉 中的点与 中所有点的边，直到连通性改变。此时这个点一定与 有连边。要确定它所属部只要再判断一下它与左右部点的边分别都断了之后的连通性即可。用二分优化这个过程即可。
询问次数是 。足以通过。时间复杂度是 的，常数较小。
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#include "graph.h"
vector<int>L,R,LR,re;
vector<pair<int,int> >S,T;
int l,r,ans,mid,i,j;
vector<int> check_bipartite(int n)
{
for(l=1,r=n-1;l<=r;query(S)?l=mid+1:(r=mid-1,ans=mid))
for(S.clear(),i=1,mid=(l+r)>>1;i<=mid;i++)S.pb(mp(0,i));
L.pb(0);R.pb(ans);LR.pb(0);LR.pb(ans);
for(i=1;i<n;i++)if(i!=ans)re.pb(i);
for(;re.size();re.erase(re.begin()+ans)){
for(l=0,r=re.size()-1;l<=r;query(S)?l=mid+1:(r=mid-1,ans=mid))
for(S.clear(),i=0,mid=(l+r)>>1;i<LR.size();i++)
for(j=0;j<=mid;j++)S.pb(mp(LR[i],re[j]));
for(S.clear(),i=0;i<LR.size();i++)
for(j=0;j<ans;j++)S.pb(mp(LR[i],re[j]));
for(T=S,i=0;i<L.size();i++)T.pb(mp(L[i],re[ans]));bool ll=query(T);
for(T=S,i=0;i<R.size();i++)T.pb(mp(R[i],re[ans]));bool rr=query(T);
if(ll&&rr)return vector<int>();
ll?L.pb(re[ans]):R.pb(re[ans]);
LR.pb(re[ans]);
}
return L;
}
附多文件编译命令（交互题本地测试）：
g++ -o code.exe code.cpp grader.cpp
后面还可以加更多cpp。