😊

AGC039 B - Graph Partition

2021/01/19に公開約600字

問題概要

グラフが与えられる
グラフを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点stとすると
kが最大になるのは頂点sV_1とし、sからの距離ごとにV_2V_3, ...と分割したものである
このときのkd+1となる
よってグラフの直径をもとめて+1すれば答えがもとまる
グラフの直径はワーシャルフロイド法で求めることができる

提出コード

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

Discussion

ログインするとコメントできます