A - NP-Hard Problem ～グラフを2部グラフ（白黒に）塗る dfs～

• Quiz
  • https://codeforces.com/contest/687/problem/A
• AC
  • https://codeforces.com/contest/687/submission/100305056
• 解説
  • 2部グラフに塗り分けられないなら-1
  • 塗り分けられるなら色ごとに分配すればいい
• その他
  • 2部グラフに塗ることは今後もありそうなので、自分用のメモとしての記事です

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,M;
    cin>>N>>M;

    VV G(N);

    rep(i,M){
      ll a,b;cin>>a>>b;
      a--;b--;
      G[a].push_back(b);
      G[b].push_back(a);
    }
    VI C(N,-1); // color

    // paint dfs
    function<void(ll,ll)> dfs = [&](ll i, ll color){
      C[i]=color;
      for(ll to : G[i]){
        if(C[to]==color)no(); // 行き先が現在地と同じ色だとNG
        if(C[to]==-1){
          dfs(to,1-color);
        }
      }
    };

    rep(i,N){
      if(C[i]==-1){
        dfs(i,0);
      }
    }
    
    VI A,B;
    rep(i,N){
      if(C[i]==0){
        A.push_back(i);
      }else{
        B.push_back(i);
      }
    }

    p(SZ(A));
    print_vector(A);
    p(SZ(B));
    print_vector(B);
    
    return 0;
}