二部グラフの判定
Coddyの「グラフ - データ構造シリーズ #9」コースのレッスン 14/14。
グラフの頂点を2つのグループに分割し、すべての辺が一方のグループの頂点ともう一方のグループの頂点を結ぶようになっている場合、そのグラフは二部グラフと呼ばれます。赤と青をイメージしてください。すべての辺は、一端が赤で、もう一端が青の頂点になっています。
BFS（幅優先探索）を使えば、明快に判定できます。任意の頂点から始めて赤色に塗り、外側に向かって探索します。新しく見つかった隣接する頂点には、直前の頂点とは反対の色を塗ります。もし、同じ色の2つの頂点を結ぶ辺が見つかった場合、そのグラフは二部グラフではありません。典型的な原因は奇数サイクルです。例えば、三角形の 0-1-2-0 では、頂点0が赤と青の両方にならざるを得なくなります。
注意点として、グラフに複数の連結成分がある場合は、それぞれの成分に対して新しく2色塗りを開始する必要があります。最も簡単なパターンは、すべての頂点を1回ループし、未着色の頂点を見つけるたびにBFSを開始することです。
チャレンジ
簡単2次元整数配列 adjacency と整数配列 vertices を受け取り、そのグラフが二部グラフ（bipartite）であれば true を、そうでなければ false を返す関数 isBipartite を作成してください。
まずグラフを構築します（各頂点に対して addVertex を行い、次に各辺に対して addEdge を行います）。その後、すべての連結成分に対して BFS を用いて2色に塗り分けます。開始点に色 0 を割り当て、各隣接する頂点には 1 - color[u] の色を割り当てます。もし、両端の頂点がすでに同じ色に塗られている辺が見つかった場合は、false を返します。それ以外の場合は true を返します。
必ず Graph クラスを使用してください（graph 内で提供されています）。隣接関係をモデル化するために言語組み込みの機能（マップ、セットなど）を使用しないでください。アルゴリズムのための補助データ（色のマップ、キューなど）には標準ライブラリの型を使用しても構いません。
自分で試してみよう
#include <stdio.h>
#include "solution.h"
int main() {
int n, m;
if (scanf("%d %d", &n, &m) != 2) return 0;
int vertices[MAX_VERTICES];
for (int i = 0; i < n; i++) scanf("%d", &vertices[i]);
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
printf("%s\n", isBipartite(adjacency, m, vertices, n) ? "true" : "false");
return 0;
}