ARC079 F： Namori Grundy
Livedoorブログからの移動
はてなブログからの移動
解き方
- 1つ閉路があり、残りはその閉路にぶらさがっているようなグラフ
- 閉路とそれ以外にまず分ける
- 閉路以外の部分は、根を0、その上を…としていくと一意に定まる
- 閉路については、適当に1頂点に
xを割り当てて、うまくいくか計算する。xは、0以上、その頂点の次元数+1 以下なので、そのパターンだけ試す。
ハマったところ
- コンテスト中はここまで考察できていなかった
- 閉路を見つける部分は、スタックを使いまわすような形式じゃないと辛い（stackにパスをpushしていくと多分
O(n^2)。関数スタックをシミュレートするような実装のほうがこの場合効率が良い） std::findはO(n)なのでループの中では厳禁。メモリに余裕のあるケースのほうが多いので一度unordered_setに変換するべき