問題

提出解答

$k \geq 2$ に対して, $(k+1)$ 頂点からなるスターグラフをレベル $k$ の星という.

いくつかの星の直和からなるグラフに対して, 以下の操作を繰り返し行い, 連結になるようにした.

その後, 各頂点に対して, $1$ から $N$ までの番号をつけた.

このグラフ $T=(V,E)$ は木になり, 次のようになっていた.

最初の状態における星の状態を求めよ.

$T$ は木であるので, 葉が存在する. その葉を $x$ とする. すると, $x$ に接続する唯一の頂点 $y$ は星の中心になっている. また, $y$ の次数は $2$ 以上であり, $y$ を中心とする星のレベルは $y$ の次数と一致する.

これにより, $y$ を中心とする星が確定したので, $y$ 及び, $y$ に接続する全ての頂点を削除することによって, 頂点数が小さい問題に帰着することができた.

これを繰り返して行くことにより, 全ての星の情報を求めることができた.

なお, 頂点を削除するとき, 削除する頂点に接続する星の中心ではない頂点が新たに葉になることに注意すること.

時間計算量は $O(N)$ 時間である.

※ なお, 実際の問題はレベルを昇順に並べる必要があり, ソートがボトルネックになって, $O(N \log N)$ 時間になる.