Codeforces #628 Div2 F. Ehab's Last Theorem

実装はこちらの方がシンプル。
https://codeforces.com/contest/1325/problem/F

問題

N頂点M辺の連結無向グラフが与えられる。
以下のいずれかを抽出せよ。

• 長さが√N以上の閉路
• √N頂点以上の独立頂点群

解法

まず、DFS順で頂点をたどり、前者を検出しよう。
もし見つからない場合、各頂点を根頂点からの距離 mod √Nで分類しよう。
ceil(√N)が3以上なので、同じグループ内の頂点同士は隣接することはない。
そこで、鳩ノ巣原理の要領で、どこかのグループは√N要素以上入るのでそれらを独立頂点群として回答すればよい。

int N,M;
vector<int> E[101010];
int D[101010];
vector<int> cand[101010];
int R;
vector<int> V;

void dfs(int cur, int pre, int d) {
	if(D[cur]>=0) {
		if(d-D[cur]>=R) {
			cout<<2<<endl;
			cout<<d-D[cur]<<endl;
			int i;
			FOR(i,d-D[cur]) cout<<(V[V.size()-1-i])<<" ";
			cout<<endl;
			exit(0);
		}
		return;
	}
	D[cur]=d;
	cand[d%(R-1)].push_back(cur+1);
	V.push_back(cur+1);
	FORR(e,E[cur]) if(e!=pre) dfs(e,cur,d+1);
	V.pop_back();
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	R=ceil(sqrt(N));
	
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	MINUS(D);
	dfs(0,0,0);
	
	FOR(i,R-1) if(cand[i].size()>=R) {
		cout<<1<<endl;
		FOR(j,R) cout<<cand[i][j]<<" ";
		cout<<endl;
		break;
	}
	
}

まとめ

Codeforcesはこういう問題時々出るよね。