Codeforces 161D (263D) Cycle in Graph

問題

n頂点m辺からなる無向グラフが与えられる。
また、整数kが与えられる。

グラフは、すべての頂点の次数がk以上である。
このグラフの長さk+1以上の閉路をどれかひとつ出力せよ。
答えが存在することは保証されている。

制約条件

n≦10^5
m≦10^5

方針

0番の頂点から適当にまだ移動していない頂点へ移動することを繰り返す。
移動できなくなったとき、最後の頂点からはk以上の辺が出ていて、
その辺の先の頂点は今までにすべて訪れている。

それらの頂点のうち、一番最初に訪れたものを選べば、
長さk+1以上の閉路ができる。

ソースコード

int n, m, k;
set<int> e[100000], f[100000];
vi ans;

void rec(int c){
	ans.pb(c);
	if(e[c].size()){
		int n = *e[c].begin();
		each(i, e[c]) e[*i].erase(c);
		rec(n);
	}
	else{
		rep(i, ans.size()) if(f[c].count(ans[i])){
			cout << ans.size() - i << endl;
			for(int j = i; j < ans.size(); j++)
			cout << ans[j] + 1 << (j==ans.size()-1?"\n":" ");
			exit(0);
		}
	}
}

int main(){
	cin >> n >> m >> k;
	rep(i, m){
		int a, b;
		cin >> a >> b;
		a--; b--;
		e[a].insert(b);
		e[b].insert(a);
	}
	rep(i, n) f[i] = e[i];
	rec(0);
	
	return 0;
}