CSAcademy Round #43 : D. Bad Triplet

Eまで解いて離脱してしまった。
https://csacademy.com/contest/round-43/task/bad-triplet/

問題

連結グラフが与えられる。
3頂点A,B,Cの組で、A-B,B-C,C-Aの最短経路長が一致するものが存在するならそれを答えよ。

解法

3つ以上の辺をもつXがあったとし、Xに隣接する3頂点をA,B,Cとする。
もしA-B間に辺があれば、X-A-Bは互いに距離1となるので条件を満たす。B-C,C-Aも同様。
いずれも辺がない場合、XをまたいでA-B,B-C,C-Aは互いに距離2となるのでやはり条件を満たす。

3つ以上の辺をもつ頂点が1つもない場合、全体が単一のループで長さが3の倍数ならループを三等分する3頂点が解となる。

int N,M;
vector<int> E[101010];
set<pair<int,int>> S;
int D[101010];
vector<int> R;

void dfs(int cur,int d) {
	if(D[cur]>=0) return;
	D[cur]=d;
	if(d*3%N==0) R.push_back(cur);
	FORR(e,E[cur]) dfs(e,d+1);
}


void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E[x].push_back(y);
		E[y].push_back(x);
		S.insert({x,y});
		S.insert({y,x});
	}
	
	for(i=1;i<=N;i++) {
		FOR(z,E[i].size()) {
			FOR(y,z) {
				if(S.count({E[i][y],E[i][z]})) {
					return _P("%d %d %d\n",i,E[i][y],E[i][z]);
				}
				else {
					FOR(x,y) {
						if(S.count({E[i][x],E[i][z]})==0 && S.count({E[i][x],E[i][y]})==0) {
							return _P("%d %d %d\n",E[i][x],E[i][y],E[i][z]);
						}
					}
				}
			}
		}
	}
	
	if(N==M && N%3==0) {
		MINUS(D);
		dfs(1,0);
		_P("%d %d %d\n",R[0],R[1],R[2]);
		return;
	}
	
	_P("-1\n");
	
}

まとめ

最後の閉路のパターンを見落としてまんまと1WAした。