Appearance
二部グラフ判定
無向グラフの頂点を2色で塗り分け、すべての辺の両端が異なる色になるか判定する。
二部グラフであることと、奇数長の閉路を持たないことは同値。
特徴
| 項目 | 内容 |
|---|---|
| 用途 | 二部グラフ判定・頂点の2グループ分け |
| 計算量 | O(V+E) |
| 空間計算量 | O(V+E)（グラフを含む） |
考え方
BFSで隣接する頂点を交互に0と1で塗る。
- 未訪問なら、現在の頂点と異なる色を設定する。
- 隣接する頂点が同じ色なら、二部グラフではない。
- 非連結グラフでは、各連結成分について探索する。
実装
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> g(n);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
vector<int> color(n, -1);
auto is_bipartite = [&]() -> bool {
queue<int> q;
for (int s = 0; s < n; s++) {
if (color[s] != -1) continue;
color[s] = 0;
q.push(s);
while (!q.empty()) {
int v = q.front(); q.pop();
for (int nv : g[v]) {
if (color[nv] == -1) {
color[nv] = color[v] ^ 1;
q.push(nv);
} else if (color[nv] == color[v]) return false;
}
}
}
return true;
};
cout << (is_bipartite() ? "Yes" : "No") << '\n';
}使用例
入力（0-indexed、無向グラフ）
text
6 4
0 1
1 2
3 4
4 5出力
text
Yes判定が成功した場合、color[v] に各頂点のグループ番号が格納される。
cpp
if (is_bipartite()) {
vector<int> a, b;
for (int v = 0; v < n; v++) {
if (color[v] == 0) a.push_back(v);
else b.push_back(v);
}
}注意点
- 二部グラフであることと、奇数長の閉路が存在しないことは同値。
- 木は必ず二部グラフ。
- 非連結グラフの場合、すべての連結成分を確認する。
- 自己ループがあれば二部グラフではない。
color = -1は未訪問、0と1はグループ番号。- グループ分けは一意とは限らない。
- 判定が失敗した場合、
colorは途中までしか設定されていない。