AGC039 B - Graph Partition

問題概要

グラフが与えられる
グラフを$V_1, V_2, .., V_k$に分割する、ただし辺は番号が隣合う集合の間のみにしか存在してはならない
$k$の最大値をもとめよ

解法

答えが存在する $\Leftrightarrow$ グラフが2部グラフである
といえる
適当な頂点を一つ取ってきて$V_i$とする、そこに隣接する頂点を$V_{i+1}$または$V_{i-1}$の集合に入れる、そして$V_{i+1}$に含まれる頂点に隣接する集合を$V_{i}$または$V_{i+2}$にいれる
というようなことをすると
偶数の番号の集合に隣接する頂点の集合は奇数の番号の集合になり、奇数の番号の集合に隣接する頂点の集合は偶数の番号の集合になる
そして偶数の番号の集合内や、奇数の番号の集合内の頂点同士に辺がなければいいということになる
これは2部グラフである

グラフの直径をdとし、距離$d$とする2点$s$、$t$とすると
$k$が最大になるのは頂点$s$を$V_1$とし、$s$からの距離ごとに$V_2$、$V_3$, ...と分割したものである
このときの$k$は$d+1$となる
よってグラフの直径をもとめて$+1$すれば答えがもとまる
グラフの直径はワーシャルフロイド法で求めることができる

提出コード

https://atcoder.jp/contests/agc039/submissions/19524211