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

Quiz

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

AC✅ (解法：二部グラフ判定＆グラフの直径）

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

解法

• 解説放送の通り、二部グラフ判定し、二部グラフなら構成可能
• 構成可能な場合、グラフの直径＋１が答え
• 必要なコードは
  • 二部グラフ判定
  • グラフの直径
• 二部グラフ判定については、蟻本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）

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

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

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

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

• ✅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