The Prufer code (1069) †

概要 †

頂点が 1 から N までで番号づけされている木に対して次の操作を実行する．

• 葉（隣接する点が 1 つしかない頂点）のうち，つけられた番号が最小である頂点を選ぶ．
• その頂点をグラフから除去する．
• その頂点に隣接していた頂点の番号を書き下す．
• 上記の操作を頂点が 1 つになるまで繰り返す．

このようにして得られた番号の列をもとの木の Prufer code と呼ぶ．Prufer code からもとの木を構成せよというのがこの問題．

解法 †

Sample Input を例として説明する．

Prufer code に 3，4，5 が含まれないことから，これらの頂点は葉であったことがわかる．なぜならば，次数が 2 以上であるとすると隣接する点のいずれかが除去されない限りその頂点は葉にはならないから．最小値は 3 であるから，最初に除去された頂点は 3 である．したがって，頂点 2 と頂点 3 はもともとつながっていたことがわかる．

さて，残りの 4 個の数字列をみると，やはり含まれていないのは 3，4，5 である．とはいえ 3 はすでに処理してしまったので，対処すべきは 4，5 ということになる．したがって 2 番目に除去された頂点は 4 であり，頂点 1，4 がつながっていたことになる．

同じようにして処理していくと，1 と 6，2 と 5，2 と 6 がそれぞれつながっていたことがわかる（後ろの 3 個からなる部分列には 1 が含まれていない点に注意）．これらの考察からもとの木は次のとおりとなる．なお，下の図では便宜的に上下を決めて書いているが，本問題では頂点間に上下関係は存在しないことに注意すること．

　　　　６
　　　／　＼
　　１　　　２
　／　　　／　＼
４　　　３　　　５

ソースコード †

1069-izumi.cpp