7K12 blog

猫でも分かるアルゴリズム解説

ABC131 E - Friendships

f:id:tkr987:20200508211122p:plain

https://atcoder.jp/contests/abc131/submissions/10950261

グラフアルゴリズムを使うわけではないので無勉でもワンチャン実装できる。

  • ウニグラフは距離2の頂点がn-1個できる (組み合わせは _{n-1}C_{2}個) 

f:id:tkr987:20200508211405p:plain

まず、距離2の組み合わせは真ん中の緑を除く頂点すべてを使って最大 _{n-1}C_{2}個できる。組み合わせ最大のときウニグラフになる。Kが最大値を超えてたら構築不可。そうでなければ、青色の辺を順次追加していくことで組み合わせを1ずつ減らして構築する。実装するとき、真ん中の頂点インデックスを1にして残りの頂点に2以降のインデックスを割り当てると楽になる。