結構面白かったです。
http://codeforces.com/contest/1033/problem/E
問題
N頂点の連結無向グラフがある。しかしその内容は頂点数以外知らされない。
このグラフが二部グラフであるか判定したい。
頂点集合を与えると、その内部の辺の数を返す関数を20000回まで使うことができる。
これを用いて、グラフが二部グラフか判定せよ。
二部グラフでないなら奇数長の閉路を1つ答えよ。
解法
戦略としては、まずスパニングツリーを作る。
スパニングツリーなら必ず二部グラフであるので、2部に分けたとき、両パート内に辺がないならグラフは二部グラフ。
もし辺が存在してしまう場合、その辺と、判明しているスパニングツリーの辺で閉路を作れる。
グラフの頂点集合をV=S+Tとなるように分割したとすると、グラフが連結なのでS,T間に最低1個の辺がある。
S={1}、T={1以外のN頂点}から初めて、前述の辺を求め、1頂点ずつTからSに頂点を動かしていこう。
そのためには、S,T間の辺を特定しなければならない。
頂点集合f,gに対し以下を考える。gは20000回使えるクエリそのものである。
f(S,T) := S,T間の辺の数
g(S) := S内の辺の数
ここで、f(S,T) = g(S∪T)-g(S)-g(T)なので、f(S,T)は具体的に求めることができる。
f(S,T)を使うと、S,T間の辺を以下の要領で二分探索できる。
- |S|=|T|=1なら、その頂点間に辺があることが確定である。
- |S|≧2の場合、S'+S''=SとなるようSを均等に2つに分割しよう。f(S',T)>0なら再帰的にS',T間の辺をS,T間の辺とみなせばよいし、f(S',T)==0ならf(S'',T)>0なので再帰的にS'',T間の辺をS,T間の辺とみなせばよい。
- |S|=1かつ|T|≧2の場合、同様にTを分割していく。
スパニングツリー構築後、二部グラフとしたとき片方の頂点集合Wに対しg(W)≧1なら、その間の辺も似た感じで特定できる。
W=W'+W''と均等に分割すると、g(W)=g(W')+g(W'')+f(W',W'')なので、右辺のどれかが正になる。
そこについて再帰的に探索していけばよい。
int N; vector<int> E[601]; int P[601]; int ask(vector<int> V) { static map<vector<int>,int> M; sort(ALL(V)); if(V.size()<=1) return 0; if(M.count(V)) return M[V]; cout<<"? "<<V.size()<<endl; FORR(v,V) cout<<(v+1)<<" "; cout<<endl; cout.flush(); int ret; cin>>ret; return M[V]=ret; } int cross(vector<int> A,vector<int> B) { vector<int> C; FORR(x,A) C.push_back(x); FORR(x,B) C.push_back(x); return ask(C)-ask(A)-ask(B); } pair<int,int> dfs(vector<int> S,vector<int> T) { int i; if(S.size()==1) { if(T.size()==1) { return {S[0],T[0]}; } else { vector<int> T2[2]; FOR(i,T.size()) T2[i%2].push_back(T[i]); if(cross(S,T2[0])) return dfs(S,T2[0]); else return dfs(S,T2[1]); } } else { vector<int> S2[2]; FOR(i,S.size()) S2[i%2].push_back(S[i]); if(cross(S2[0],T)) return dfs(S2[0],T); else return dfs(S2[1],T); } } void dfs2(int cur,int pre,int id) { P[cur]=id; FORR(e,E[cur]) if(e!=pre) dfs2(e,cur,id+1); } void dfs3(int cur,int tar,vector<int>& T) { if(cur==tar) { cout<<"N "<<T.size()+1<<endl; FORR(t,T) cout<<(t+1)<<" "; cout<<(tar+1)<<endl; exit(0); } FORR(e,E[cur]) if(T.empty() || e!=T.back()) { T.push_back(cur); dfs3(e,tar,T); T.pop_back(); } } void check(vector<int> S) { if(ask(S)==0) return; int i; vector<int> S2[2]; FOR(i,S.size()) S2[i%2].push_back(S[i]); check(S2[0]); check(S2[1]); pair<int,int> p=dfs(S2[0],S2[1]); vector<int> T; dfs3(p.first,p.second,T); } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; vector<int> S,T; S.push_back(0); for(i=1;i<N;i++) T.push_back(i); while(T.size()) { pair<int,int> p=dfs(S,T); E[p.first].push_back(p.second); E[p.second].push_back(p.first); S.push_back(p.second); T.erase(find(ALL(T),p.second)); } dfs2(0,0,0); S.clear(); T.clear(); FOR(i,N) { if(P[i]%2==0) S.push_back(i); else T.push_back(i); } check(S); check(T); cout<<"Y "<<S.size()<<endl; FORR(s,S) cout<<(s+1)<<" "; cout<<endl; }
まとめ
面白いけど自力で時間内に思いつく気がしないな。