TopCoder SRM 682 Div1 Easy SmilesTheFriendshipUnicorn

しょうもないミスをした。
https://community.topcoder.com/stat?c=problem_statement&pm=14162

問題

N頂点M辺の無向グラフが与えられる。
異なる5頂点A～Eの組で、A-B-C-D-Eが順に辺でつながっているようなものが存在するか。
各頂点は連結しているこが保証される。

解法

Nの割にMが小さい点に着目しよう。

まずCを総当たりする。
各Cに対し、異なる隣接点２個を総当たりし、B,Dの候補としよう。
Nは大きいのでパッと見O(N^3)に見えるが、Mが小さいのでせいぜいO(M^2)で済む。

これでB-C-Dまで求めることができたので、あとはA,Eの候補の有無を確かめればよい。
BにC,D以外の隣接点の存在、及びDにB,C以外の隣接点の存在するかを、頂点の次数を用いて確認する。
それぞれそのような点が存在するなら、それらをA,EとすればA-B-C-D-Eの関係になる5頂点が選べる。

例外として、A=Eとなる可能性があるが、この場合も問題ない。
この場合、A-B-C-D-Aと閉路が出来ていることになる。
問題文の条件より、A～Dのどれかは、閉路外の隣接点を1個以上持つので、A～Dにそれを加えると題意を満たす頂点の選び方が可能となる。

int M[2020][2020];
vector<int> E[2020];
int dist[2020];

class SmilesTheFriendshipUnicorn {
	public:
	
	string hasFriendshipChain(int N, vector <int> A, vector <int> B) {
		int i,x,y;
		
		ZERO(M);
		FOR(i,N) E[i].clear();
		FOR(i,A.size()) {
			E[A[i]].push_back(B[i]);
			E[B[i]].push_back(A[i]);
			M[A[i]][B[i]]=M[B[i]][A[i]]=1;
		}
		FOR(i,N) {
			FOR(y,E[i].size()) FOR(x,y) {
				int xx=E[i][x], yy=E[i][y];
				int ok=0;
				if(E[xx].size()>2 || (E[xx].size()==2&&M[xx][yy]==0)) ok++;
				if(E[yy].size()>2 || (E[yy].size()==2&&M[xx][yy]==0)) ok++;
				if(ok==2) return "Yay!";
			}
		}
		return ":(";
		
	}
}

まとめ

考察は面倒だけど、実装はそれほどでもない。
300ptらしい問題だね。