Hatena::Grouptopcoder

thorikawa@top coder

topcoder id: the_poly
 | 

2013-02-18

TopCoder - TCO 2012 Round 3A

| 14:54 | はてなブックマーク -  TopCoder - TCO 2012 Round 3A - thorikawa@top coder

グラフ強化月間と題して自習。TCO 2012 Round3Aは250,600ともにグラフ問題。

250 ChromaticNumber

各頂点から出ていくエッジが最低でもN-3あることから、逆にエッジがない部分をエッジとしてグラフを反転してやる(つまりエッジが無い=色が異なる)。この反転グラフを連結成分分解すると、各連結成分間にはエッジが存在しないので、同じ色は使われず、各連結成分ごとに必要な色数を求めて足せば、求める答えとなる。

各連結成分は、各頂点から出て行くエッジ数が高々2であることから、分岐のない一本道のグラフとなり、頂点数が3でcyclicの場合に1色、それ以外は2頂点ごとに色を変えていくことになるので、頂点数nに対しn/2+n%2色が必要となる。

ソース

https://gist.github.com/thorikawa/4975164

600 FoxAndCake

あとでやる。

 |