自習 | |
グラフ強化月間と題して自習。TCO 2012 Round3Aは250,600ともにグラフ問題。
各頂点から出ていくエッジが最低でもN-3あることから、逆にエッジがない部分をエッジとしてグラフを反転してやる（つまりエッジが無い＝色が異なる）。この反転グラフを連結成分分解すると、各連結成分間にはエッジが存在しないので、同じ色は使われず、各連結成分ごとに必要な色数を求めて足せば、求める答えとなる。
各連結成分は、各頂点から出て行くエッジ数が高々2であることから、分岐のない一本道のグラフとなり、頂点数が3でcyclicの場合に1色、それ以外は2頂点ごとに色を変えていくことになるので、頂点数nに対しn/2+n%2色が必要となる。
ソース
https://gist.github.com/thorikawa/4975164
あとでやる。
