bipartite_coloring
関数 · 二部グラフ判定と 2 彩色
template <graph_type G>
std::optional<std::vector<int>> bipartite_coloring(const G &g);
概要
二部グラフ判定と 2 彩色
2 彩色は連結成分ごとに色の入れ替えを除いて一意なので、 各成分で大きい側を色 0 に選ぶことで色 0 の頂点数を全体で最大化する （同数なら成分の代表頂点側を色 0 とする）。 色 1 を最大化したい場合は全頂点の色を反転すればよい。
テンプレートパラメータ
| 名前 | 説明 |
|---|---|
G |
グラフ型（無向グラフを想定、list_graph<T> / csr_graph<T> のいずれでも可） |
戻り値
二部グラフなら各頂点の色（0/1）の割り当て、そうでなければ std::nullopt
計算量
- $O(V+E)$