[ABC327] D - Good Tuple Problem

[Q] D - Good Tuple Problem

考察
1. 二部グラフが作れるかどうかを聞かれているので、判定をしたい。
2. 普通にグラフを張る。
3. 頂点0からdfsをスタート。スタートの色は0で固定する。
4. 自分が0なら、1手先の色は1に。次は0に。を進めていく。矛盾があればNo
5. スタートする頂点をNまで確認。スタートの色が定まっているならスルー。矛盾があればNo
6. 矛盾がなければYes

実装

int main() {
  cincout();
  ll N, M;
  cin >> N >> M;

  // グラフをはる
  vector<ll> G[N];
  vector<ll> A, B;
  rep(i, M) {
    ll a;
    cin >> a;
    --a;
    A.push_back(a);
  }
  rep(i, M) {
    ll b;
    cin >> b;
    --b;
    B.push_back(b);
  }
  rep(i, M){
    G[A[i]].push_back(B[i]);
    G[B[i]].push_back(A[i]);
  }
  
  // 色をぬる
  vector<ll> col(N, -1);
  function <void(ll)> dfs = [&](ll v){
    for(auto u : G[v]){
      if (col[u] == -1){
        col[u] = col[v] ^ 1;
        dfs(u);
      }
      else if(col[v] == col[u]){ // 矛盾があればNo
        cout << "No" << endl;
        exit(0);
      }
    }
  };
  rep(i, N){
    if (col[i] == -1){
      col[i] = 0;
      dfs(i);
    }
  }
  // 矛盾がなければYes
  cout << "Yes" << endl;
}

https://atcoder.jp/contests/abc327/submissions/47240341