yukicoder : No.408 五輪ピック

似た問題どこかで見たけどなんだったかな…。
http://yukicoder.me/problems/no/408

問題

N頂点M辺の無向グラフが与えられる。
頂点1を含む異なる５点からなる閉路が存在するか求めよ。

解法

頂点1から距離2の点vを列挙しよう。
その際経由した点(すなわち頂点1とvの間の点)uも列挙する。
すなわち1-u-vという関係にある(u,v)を列挙し、各vに対し経由点uの候補を覚えておこう。

1-u-vという点の並びと1-u'-v'という点の並びがあるとき、以下の条件を満たせば1-u-v-v'-u'-1という閉路ができる。

• 1,u,v,u',v'が異なる
• vとv'の間に辺がある

逆に元のグラフにa-bという辺があったとき、aをv、bをv'と見なして上記関係が成り立つかどうか見る。
aとbは異なるのでvとv'は異なるのは明らかだし、(u,v)の作り方よりuとv、u'とv'が異なるのは明らか。
問題はuやu'がv,v'と一致しないことを判定しなければならない。

v,v'の経由点がそれぞれ３つ以上あるなら、重複しないu,u'を選ぶことができる。
またどちらかの経由点2個以下なら、u,u'を総当たりして重複しないものがあるか探索しよう。

int N,M;
vector<int> E[202020];
vector<int> C[202020];
int yes[202020];
vector<int> S;
int A[505050],B[505050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>A[i]>>B[i];
		A[i]--;
		B[i]--;
		E[A[i]].push_back(B[i]);
		E[B[i]].push_back(A[i]);
	}
	
	FORR(e,E[0]) FORR(f,E[e]) if(f!=0) C[f].push_back(e);
	
	FOR(i,M) {
		if(A[i]==0) continue;
		if(B[i]==0) continue;
		
		if(C[A[i]].size()>3 && C[B[i]].size()>3) return _P("YES\n");
		FORR(a,C[A[i]]) {
			FORR(b,C[B[i]]) {
				if(a!=b && a!=B[i] && b!=A[i]) return _P("YES\n");
			}
		}
		
	}
	
	_P("NO\n");
	
}

まとめ

無駄にDFSして時間ロスした。
まぁ間に合わないだろうと思ったけどさ。