早稲田大学プログラミングコンテスト2019 C - Permutation City
解法
木にする
まずはグラフの形を簡単にします。距離に関する条件が「1または2である」ということ、そして「条件を満たす順列は必ず存在する」と書かれていることから、
- 連結性を保ったままいくつかの辺を削除しても、変化後のグラフに対する答えは存在する。
- 変化後のグラフに対して求めた答えは、元のグラフに対する答えにもなっている。
ことが分かります。2番目の性質は、変化後のグラフで距離が1または2である頂点対は、辺を足して元のグラフに戻しても距離が1または2であることから分かります。
そのため考えやすいように木にしてしまいましょう。例えばUnion-Findを用いて、辺を1本ずつ入力から受け取りながら既に両端が連結な辺については無視することで、全域木を得ることが出来ます。
答えを求める
答えの構成方法として最も簡単なのは、どの頂点間の距離も1または2であるような2頂点以上のグループに分割し、その中で頂点番号をローテーションすることです。
このように2頂点以上のグループを作ることが重要です。1頂点だけだと頂点番号が動かないので、距離が1または2ではなく0になってしまいます。
どの頂点間の距離も1または2であるようなグループとして、作りやすいのは深さ1の木です。先ほどグラフを木にしたので、これを深さ1の木に分割していくことを考えます。
根付き木にして葉のほうからグループを作っていきます。具体的には各頂点について、
- 自分の子のうち「グループに入っていない」状態の子が1つでもあれば、そのような子と自分自身でグループを作る。
- そうでない場合、自分を「グループに入っていない」状態にする(親とグループになる)。
と処理していくと条件を満たすグループを作れます。以下の図がそのようなグループ分けの例です。
ただしこの方法だと、運が悪いと根が孤立してしまいます。これを防ぐ方法としては、最初に根を選ぶ時には次数1の頂点を選び、根が孤立しそうな時は唯一の子が根をグループに入れてあげると良いです。
各グループについて頂点番号をローテーションしたものを答えとして出力すればOKです。