Codeforces #161 Div2. D. Cycle in Graph

さて４問目。
http://codeforces.com/contest/263/problem/D

N個の点からなるグラフで、各点は必ずK本以上の辺をもつ。
そのうち、K+1個以上の点を通る閉路を出力する問題。

各点K本の辺をもつので、適当に未到達点を辿ってもK+1個の点まではたどり着く。
後は最初の点に戻ればよい。

ただ、最初の点の選び方を間違えると最初に戻れない。
たとえばK=2の時、始点が２つのK=2な完全グラフに1本ずつつながっている場合、その始点に戻れない。
とはいえ、その場合でもどこかに閉路を含むグラフがあるはずである。

よって乱拓で対応してみた。
最初の点だけランダムで選び、後はBFSで閉路を探し、ダメなら最初の点を選びなおす。

int N,M,K;
vector<int> E[100001];
int vis[100001];
vector<int> p;

void solve() {
	int f,r,i,j,k,l,cur,tar,ret,loop;
	int x,y,mx,my;
	double sx,sy,tx,ty,tmx,tmy,ma,sc;
	double msc;
	
	GET3(&N,&M,&K);
	K++;
	FOR(i,M) {
		j=GETi()-1;
		k=GETi()-1;
		E[j].push_back(k);
		E[k].push_back(j);
	}
	srand(time(NULL));
retry:
	p.clear();
	ZERO(vis);
	ret=cur=rand()%N;
	while(1) {
		int pcur=cur;
		vis[cur]=1;
		p.push_back(cur);
		
		if(p.size()>=K) {
			FOR(i,E[cur].size()) {
				tar=E[cur][i];
				if(tar==ret) {
					cur=ret;
					break;
				}
			}
			if(cur==ret) break;
		}
			
		FOR(i,E[cur].size()) {
			tar=E[cur][i];
			if(vis[tar]) continue;
			cur=tar;
			break;
		}
		if(cur==pcur || p.size()>N) goto retry;
	}
	
	_P("%d\n",p.size());
	FOR(i,p.size()) {
		if(i!=0) _P(" ");
		_P("%d",p[i]+1);
	}
	_P("\n");
	
	return;
}

まとめ

最初「必ず閉路になるとは限らない点もある」ってことに気づかず苦戦した。