这是一道交互题
交互库有 \(n\) 个点 \(m\) 条边的简单无向连通图，至多 \(2000\) 次询问一个边集 \(E‘\)，交互库告诉你把 \(E‘\) 中的边去掉之后图是否连通。求这张图是不是二分图，如果是则求一侧。
\(2\le n\le 200\)。
\(n^2\) 次询问就可以把整个图求出来，拿到了丢人的 \(37\) 分。
又忘了，连通无向图->生成树。
可以 bfs 把生成树求出来，每次找出当前点连出的所有边，可以直接大力二分，最后求出染色方案并 check 一下。
check 染色方案就枚举一条树边断掉，并把除树边外的异色边断掉，如果连通说明不合法。
总询问次数大约 \((\lceil\log_2n\rceil+2)n\)。
#include<bits/stdc++.h>
#include"graph.h"
#define PB emplace_back
using namespace std;
typedef vector<int> VI;
typedef pair<int, int> pii;
const int N = 203;
int Q[N], fr, re;
VI q, ans, G[N];
vector<pii> now, tmp, edg;
bool col[N], vis[N], fal[N][N], tre[N][N];
int work(int u){
if(q.empty()) return -1;
int l = 0, r = q.size()-1, md;
auto qry = [&](int r){
tmp = now;
for(int i = 0;i <= r;++ i)
tmp.PB(u, q[i]);
return query(tmp);
};
if(qry(r)){
for(int i = 0;i <= r;++ i){
fal[u][q[i]] = fal[q[i]][u] = true;
now.PB(u, q[i]);
}
return -1;
}
while(l < r)
qry(md = l+r>>1) ? l = md+1 : r = md;
for(int i = 0;i < l;++ i){
fal[u][q[i]] = fal[q[i]][u] = true;
now.PB(u, q[i]);
}
return q[l];
}
void dfs(int x, int f){
for(int v : G[x]) if(v != f){
col[v] = !col[x]; dfs(v, x);
}
}
VI check_bipartite(int n){
vis[0] = true; Q[re++] = 0;
while(fr < re){
int u = Q[fr]; q.resize(0);
for(int i = 0;i < n;++ i)
if(!vis[i] && !fal[u][i]) q.PB(i);
int v = work(u);
if(v == -1){++fr; continue;}
Q[re++] = v;
tre[u][v] = tre[v][u] = vis[v] = true;
G[u].PB(v); G[v].PB(u); edg.PB(u, v);
}
dfs(0, 0);
tmp.resize(0);
for(int i = 0;i < n;++ i) if(!col[i])
for(int j = 0;j < n;++ j) if(col[j] && !tre[i][j])
tmp.PB(i, j);
tmp.PB();
for(int x = 0;x < n-1;++ x){
tmp.back() = edg[x];
if(query(tmp)) return VI();
}
for(int i = 0;i < n;++ i) if(!col[i]) ans.PB(i);
return ans;
}