Hidden Bipartite Graph
题意
交互题。有一个 \(n \le 600\) 的图，你可以询问至多 \(20000\) 次。每次问一个点集 \(S\)，返回满足两个端点都在 \(S\) 中的边的个数。你需要判断这个图是不是二分图，如果是，则分别输出左部和右部的点，否则按顺序输出任意一个奇环。
思路
先判断二分图。一个十分巧妙的方法是，先找出一棵生成树，然后染色，然后再拓展判断是否是二分图。这样做是因为生成树是好找的（图保证连通），而且树是特别的二分图。
现在我们任意找出一棵生成树。我们发现判断一个点 \(x\) 和一个点集 \(S\) 有没有连边是容易的，只需要先问 \(S+x\)，然后再问 \(S\)，然后相减。
设已经连通的点集为 \(T\)，剩余点集为 \(S\)。初始 \(T=\{1\},S=2 \sim n\)。
找树边的时候我们逮住 \(T\) 的一个点 \(x\)，然后二分的方式找出和它相连的所有点，并把这些点加入 \(T\)，然后 \(x\) 的使命就结束了了，可以把它从 \(T\) 删除，因为它无法再用来更新边了。
这样每个点加入生成树最多要 \(2 \log n\) 次询问，一共 \(2n \log n\) 左右，大概 \(10800\)。
然后我们就找到了一棵生成树。然后给这棵树黑白染色，就是奇数层染黑色，偶数层染白色。然后黑、白两个点集分别查询一下内部是否有边，如果没有，那么这两个点集就是二分图的左右部，否则不存在二分图。
如果不存在二分图，我们还需要找一个奇环。只要生成树上奇数层和奇数层或者偶数层和偶数层有连边，就行成了一个奇环。环包括书上路径和非树边的那一条边。因此我们对于每个奇数层的点（当然偶数层也同理可以），采用同样的方式二分所有奇数层的点（除去它自己），先判断一下有没有连边，如果有就找到一个和它有连边的点。一共大概 \(2n+2 \log n\) 次询问。完全足够。
总共询问次数大概 \(2 n \log n + 2n + 2 \log n\)。
code
#include<bits/stdc++.h>
//#define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
const int N=1000;
int n;
vector<int> res;
int st[N],top;
int m;
int dep[N],fa[N];
vector<int> to[N];
int write(vector<int> &vec,int l,int r) {
if(r-l+1<2) return 0;
cout<<"? "<<r-l+1<<endl;
rep(i,l,r) cout<<vec[i]<<' ';
cout<<endl;
cin>>m;
return m;
}
int write(vector<int> &vec,int l,int r,int y) {
if(r-l+1<=0) return 0;
cout<<"? "<<r-l+1+1<<endl;
rep(i,l,r) cout<<vec[i]<<' ';
cout<<y<<endl;
cin>>m;
return m;
}
int write(int x,int y) {
cout<<"? 2"<<endl;
cout<<x<<' '<<y<<endl;
cin>>m;
return m;
}
vector<int> del;
void solve(int u,int l,int r) {
if(l==r) {
int m=write(u,res[l]);
if(m) del.push_back(l),st[++top]=res[l],to[u].push_back(res[l]),to[res[l]].push_back(u);
return;
}
int m=write(res,l,r,u)-write(res,l,r);
if(!m) return;
int mid=(l+r)>>1;
solve(u,l,mid);solve(u,mid+1,r);
}
vector<int> lb,rb;
int col[N];
void dfs(int u) {
if(col[u]==1) lb.push_back(u);
else rb.push_back(u);
for(int v:to[u]) {
if(col[v]) continue;
dep[v]=dep[u]+1;fa[v]=u;
col[v]=col[u]==1?2:1;
dfs(v);
}
}
bool check() {
if(lb.size()>=2) {
cout<<"? "<<lb.size()<<endl;
for(int u:lb) cout<<u<<' ';
cout<<endl;
cin>>m;
if(m) return 0;
}
if(rb.size()>=2) {
cout<<"? "<<rb.size()<<endl;
for(int u:rb) cout<<u<<' ';
cout<<endl;
cin>>m;
if(m) return 0;
}
return 1;
}
bool check(vector<int> &vec,int u) {
return write(vec,0,vec.size()-1,u)-write(vec,0,vec.size()-1);
}
bool check(int u,vector<int> &vec,int l,int r) {
return write(vec,l,r,u)-write(vec,l,r);
}
int find(int u,vector<int> &vec,int l,int r) {
if(l==r) return vec[l];
int mid=(l+r)>>1;
if(check(u,vec,l,mid)) return find(u,vec,l,mid);
else return find(u,vec,mid+1,r);
}
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
// freopen("my.out","w",stdout);
#endif
cin>>n;
rep(i,2,n) res.push_back(i);
st[++top]=1;
while(!res.empty()) {
int u=st[top--];
solve(u,0,(int)res.size()-1);
vector<int> tmp;
sort(del.begin(),del.end());
int op=0;
rep(i,0,(int)res.size()-1) {
if(op<(int)del.size()&&i==del[op]) op++;
else tmp.push_back(res[i]);
}
del.clear();
res=tmp;
}
col[1]=1;
dep[1]=1;
dfs(1);
if(check()) {
sort(lb.begin(),lb.end());
int k=unique(lb.begin(),lb.end())-lb.begin();
cout<<"Y "<<k<<endl;
for(int j=0;j<k;j++) cout<<lb[j]<<' ';
cout<<endl;
}else{
rep(i,0,(int)lb.size()-1) {
vector<int> tmp;
rep(j,0,i-1) tmp.push_back(lb[j]);
rep(j,i+1,(int)lb.size()-1) tmp.push_back(lb[j]);
if(check(tmp,lb[i])) {
int x=find(lb[i],tmp,0,tmp.size()-1);
vector<int> lp,lp2;
int y=lb[i];
if(dep[x]<dep[y]) swap(x,y);
while(dep[x]>dep[y]) {
lp.push_back(x);
x=fa[x];
}
while(x!=y) {
lp.push_back(x),lp2.push_back(y);
x=fa[x],y=fa[y];
}
lp.push_back(x);
cout<<"N "<<lp.size()+lp2.size()<<endl;
for(int u:lp) cout<<u<<' ';
for(int k=lp2.size()-1;k>=0;k--) cout<<lp2[k]<<' ';
cout<<endl;
return 0;
}
}
rep(i,0,(int)rb.size()-1) {
vector<int> tmp;
rep(j,0,i-1) tmp.push_back(rb[j]);
rep(j,i+1,(int)rb.size()-1) tmp.push_back(rb[j]);
if(check(tmp,rb[i])) {
int x=find(rb[i],tmp,0,tmp.size()-1);
vector<int> lp,lp2;
int y=rb[i];
if(dep[x]<dep[y]) swap(x,y);
while(dep[x]>dep[y]) {
lp.push_back(x);
x=fa[x];
}
while(x!=y) {
lp.push_back(x),lp2.push_back(y);
x=fa[x],y=fa[y];
}
lp.push_back(x);
cout<<"N "<<lp.size()+lp2.size()<<endl;
for(int u:lp) cout<<u<<' ';
for(int k=lp2.size()-1;k>=0;k--) cout<<lp2[k]<<' ';
cout<<endl;
return 0;
}
}
}
}