概要

頂点数nで、辺の数がmのグラフが与えられているとする。隣接する頂点同士が違う色になるように二色で塗り分けられるならばそのグラフを二部グラフという。

判定するグラフ

n m
V_i1 V_j1
V_i2 V_j2
.....
V_im V_jm

1行目は頂点数nと辺の数m、2行目からm+1行目まではそれぞれ頂点V_iと頂点V_jが辺で結ばれていることを示す。

判定プログラム例

二部グラフであれば"Yes", そうでなければ"No"と出力。

bipartiteG.cpp

#include <iostream>
#include <vector>
using namespace std;

const int MAXN=128;
vector<int> G[MAXN];
int color[MAXN];

int main() {
    int n,m; cin>>n>>m;
    for(int i=0; i<m; ++i) {
        int a,b; cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    fill(color, color+n, -1);

    color[0]=0;
    bool ok=true;
    for(int i=0; i<n; ++i) {
        for(int j=0,size=G[i].size(); j<size; ++j) {
            if(color[G[i][j]]==color[i]) { ok=false; i=n; j=size; }
            else { color[G[i][j]] = !color[i]; }
        }
    }
    cout << (ok ? "Yes":"No") << endl;
    return 0;
}

実行例

ex.1

bipartiteG.in

4 4
0 1
0 3
1 2
2 3

出力

$ g++ -Wall bipartiteG.cpp && ./a.out < bipartiteG.in
Yes

ex.2

bipartiteG.in

3 3
0 1
0 2
1 2

出力

$ g++ -Wall bipartiteG.cpp && ./a.out < bipartiteG.in
No

競技プログラミングの基本処理チートシート (C++)
概要 限られた時間の中で問題を解くために必要となる、競技プログラミングにおける基本的な処理のチートシートです。競プロにおけるメジャー言語 C++ を利用します。その際 C++11 の機能は利用せず C++03 の機能の範囲内で記述します。 頻度高く定期的に開催されるコンテスト AtCoder Codeforces