五輪ピック [yukicoder 408] - はまやんはまやんはまやん

問題

N頂点、M辺の単純無向グラフがある。
各頂点には1からNの番号がついている。
このグラフ上で頂点1を含む長さ5の単純閉路があれば"YES"、なければ"NO"

2 <= N <= 2*10^4
0 <= M <= 5*10^4

帰納的考察（解説見た）

1. 頂点数の制約は普通 O(n log n) 解答かな？
2. DFSというのもありそう(頂点1を含むというのが気になる)
3. 辺の制約も気になる
4. 気になる…
5. 気になる…

――壁――

6. 何かを全列挙するのでは無いか？？と考える
7. 今回全列挙できものとして考えられるものの1つが「辺」
8. 辺についてのクエリがO(1)で捌ければ、解が求まる
9. そういう感じに考えると解説のような解答ができる

10. ある両端のどちらも0でない辺に対して、その両端から0への長さ2の使う頂点が異なったパスが存在するかを判定する
11. O(1)に抑えるために前計算が必要
12. C[i]を頂点0から頂点iへの長さ2のパスで使われる真ん中の頂点の集合とする
13. これを用いると、以下のように、ある辺に対して単純閉路があるか判定できる

ある辺(i,j)に対して、
C'[i] = C[i] - j
C'[j] = C[i] - i
とすると、

|C'[i]| = |C'[j]| = 1 かつ C'[i] != C'[j]
1 <= |C'[i]|, |C'[j]| かつ 2 <= max(|C'[i]|, |C'[j]|)

のどちらかを満たせば、単純閉路が存在する

14. 解説どおり実装したら通った
15. 解説にはunordered_setとありましたが、普通のsetでも大丈夫でした

実装

http://yukicoder.me/submissions/109487

int N, M;
vector<int> E[101010];
//-----------------------------------------------------------------
unordered_set<int> C[101010];
string solve() {
	for (int i : E[0]) for (int j : E[i]) {
		if (j == 0) continue;
		C[j].insert(i);
	}

	rep(i, 0, N) for (int j : E[i]) {
		if (j < i) continue;
		if (i == 0 || j == 0) continue;

		int num_i = C[i].size();
		if (C[i].count(j)) num_i--;
		int num_j = C[j].size();
		if (C[j].count(i)) num_j--;

		if (num_i == 1 && num_j == 1) {
			int a;
			for (int k : C[i]) if (k != i && k != j) a = k;
			int b;
			for (int k : C[j]) if (k != i && k != j) b = k;
			if (a != b) return "YES";
		}

		if (1 <= num_i && 1 <= num_j) {
			int m = max(num_i, num_j);
			if (2 <= m) return "YES";
		}
	}

	return "NO";
}
//-----------------------------------------------------------------
int main() {
	cin >> N >> M;
	rep(i, 0, M) {
		int A, B;
		scanf("%d %d", &A, &B);
		A--; B--;

		E[A].push_back(B);
		E[B].push_back(A);
	}
	cout << solve() << endl;
}