[AtCoder] ABC146 D – Coloring Edges on Tree (400点)

2019年11月30日AtCoderグラフ, , 400点, BFS, 辺彩色

問題

木構造について、頂点から見た時に自身から伸びる枝に重複が無いように色を塗る。使う色の数の最小値はいくつか?

問題:D – Coloring Edges on Tree

(木構造はグラフの一種と捉えられるので、グラフの辺彩色と言うこともあります。)

解法

どの頂点からでも、使う色が最小になるように幅優先探索をしながら枝を彩色していくと、使う色の数が最小になります。

注意点

頂点数はNですが、最大値は\(10^5\)となっています。グラフを隣接行列で表現しようとすると、\(10^{10}\)に比例したメモリを使用することになります。int型で保持するなら1Bのデータが\(10^{10}\)個必要なので、10GBのメモリが必要になってしまいます。

このような場合は隣接リスト表現を用いると良いでしょう。

(隣接行列や隣接リスト行列についてはグラフを参照のこと)

プログラム例

C++での例