Lyft Level 5 Challenge 2018 - Elimination Round : E. Hidden Bipartite Graph

結構面白かったです。
http://codeforces.com/contest/1033/problem/E

問題

N頂点の連結無向グラフがある。しかしその内容は頂点数以外知らされない。
このグラフが二部グラフであるか判定したい。

頂点集合を与えると、その内部の辺の数を返す関数を20000回まで使うことができる。
これを用いて、グラフが二部グラフか判定せよ。
二部グラフでないなら奇数長の閉路を１つ答えよ。

解法

戦略としては、まずスパニングツリーを作る。
スパニングツリーなら必ず二部グラフであるので、２部に分けたとき、両パート内に辺がないならグラフは二部グラフ。
もし辺が存在してしまう場合、その辺と、判明しているスパニングツリーの辺で閉路を作れる。

グラフの頂点集合を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;
	
	
}

まとめ

面白いけど自力で時間内に思いつく気がしないな。