頂点数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