2部グラフの判定

初めに

この問題をやっていて
https://atcoder.jp/contests/abc282/tasks/abc282_d
2部グラフが分かっていないとおそらく解けない問題だった

2部グラフ自体は結構単純な方法で実装できる
かなり汚い書き方になっているがわかりやすくていいのではないかと思っている
あとはこういうのをぼちぼちテンプレート的な書き方にして直していきたいなあ

fn dfs_nibu(nibu: &mut Vec<usize>,g:&Vec<Vec<usize>>,start:usize,mut color:usize)->bool{
  nibu[start] = color;
  for i in &g[start]{
    if nibu[*i] != 0{
      if nibu[*i] == 1 && nibu[start] == 1{
        return false;
      }else if nibu[*i] == 2 && nibu[start] == 2{
        return false;
      }else{
        continue
      }
    }
 
    if nibu[start] == 1{
        color = 2;
    }else if nibu[start] == 2{
        color = 1;
    }
 
let flag = dfs_nibu(nibu,g,*i,color);
    if flag == false{
      return false;
    }
}
return true;
}
 
 
fn main() {
  input!{
  n:usize,
  m:usize,
  a:[[usize;2];m]
  }
  let mut s = vec![vec![];n];
  let nn = n as i64;
 
  for i in a {
    s[i[0]-1].push(i[1]-1);
    s[i[1]-1].push(i[0]-1);
  }

let mut nibu = vec![0;n];

for i in 0..n{
  if nibu[i] != 0{continue}
 
let flag = dfs_nibu(&mut nibu,&s,i,1);
if flag == false{
  println!("{}",0);
  return;
} 
 ///2部グラフが複数あり、探索済みを記憶させておく（連結成分が複数あるという言い方するみたい）
  for i in 0..n{
    if nibu[i] != 0 {
      nibu[i] =3;
    }
  }
}
  
}