B - Graph Partition ~二部グラフ判定&"グラフの"直径(by WF)~

Quiz

https://atcoder.jp/contests/agc039/tasks/agc039_b

AC✅ (解法:二部グラフ判定&グラフの直径)

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

解法

  • 解説放送の通り、二部グラフ判定し、二部グラフなら構成可能
  • 構成可能な場合、グラフの直径+1が答え
  • 必要なコードは
    • 二部グラフ判定
    • グラフの直径
  • 二部グラフ判定については、蟻本p94にある通りdfsする
  • グラフの直径については、ワーシャルフロイドして全点間距離を求め、その中の最大値が直径
const int N_MAX = 205;
ll N; 
ll d[N_MAX][N_MAX]; // 隣接行列 ワーシャルフロイド用
VV G; // 隣接グラフ dfs用

// 二部グラフかどうか
// 蟻本 p94
int color[N_MAX];
bool dfs(int v, int c){
  color[v] = c;
  for(ll to : G[v]){
    if(color[to]==c) return false;
    // 隣接している頂点がまだ塗られていないなら-cで塗る
    if(color[to]==0 && !dfs(to, -c)) return false;
  }
  // すべての頂点を正しく塗れたらtrue
  return true;
}
bool is_bipartite(){
  if(dfs(0, 1)==true){
    return true;
  }else{
    return false;
  }
}

おまけ解法(BFS)

f:id:peroon:20191006074002p:plain

  • コンテスト中はこちらで解いた https://atcoder.jp/contests/agc039/submissions/7868873
  • どこかの点からBFS
  • 訪れていない隣接点のセットが得られる。そのセット内で辺があれば打ち切り
  • 隣接点のセットから、次の隣接点セットを得る。繰り返し
  • それを全点を開始点として試し、最大のkを求める

そのBFS解法、任意の1点から開始だとどうなる?

  • 最大値が得られない場合がある。なので全点を始点として試す必要がある

f:id:peroon:20210609065605j:plain

追記:ライブラリを整備した

  • https://atcoder.jp/contests/agc039/submissions/23303982
    • ✅二部グラフ判定
    • ✅グラフの直径 by WF
    • ?木の直径 by bfs (今回の設定は木ではない)
  • ⚠️学び:木の直径なのか、グラフの直径なのか注意する。木の場合のみbfs or dfsの手法が使える

他に「二部グラフ判定」を使う問題

C - 3 Steps https://atcoder.jp/contests/code-festival-2017-qualb/tasks/code_festival_2017_qualb_c