Codeforces 411 Div.1C Ice cream coloring
ツリーTが与えられて、Tの各頂点v[i]にアイスクリームの集合s[i]が与えられる。同一のアイスが含まれる頂点だけからなる部分グラフは連結である。この時、新しいアイスの集合を頂点とするグラフGを、Tのある頂点v[i]があって、アイスaとアイスbがs[i]に含まれるならば、aとbの間に無向エッジを貼る。この時、Gの最小Coloringを構成せよ。
Gにおいて、Tの各頂点に対応するs[i]に含まれる元ついてはクリークとなる。さらに、部分グラフが連結であるという条件から、二つのクリーク同士を接続する頂点集合もクリークとなる(つまり二つの独立したクリークで接続されていることはない)。なのでクリークごとに貪欲に色を決めていけば良い。
つまり、dfsで各クリークを見ていったとして、その時点で着色可能であった色が、別の頂点の探索中で棄却されることはない。
そのためTのある頂点からdfsする。今見ている頂点がGのクリークに対応する。Colorを数字で表した時、既に着色済みの頂点を除いて小さい方から貪欲に色をつけていく。O(V)。
