二分图

定义

对于一张无向图 \(G\)，若所有点可以分为两个点集 \(A\) 和 \(B\)，且 \(A\) 和 \(B\) 的内部没有连边，那么我们称 \(G\) 可以划分为一张二分图。

• 二分图的划分不唯一，也不一定联通，也不一定有环

存在的充要条件

若无向图 \(G\) 是二分图，那么 \(G\) 没有奇环。

若无向图 \(G\) 没有奇环，那么 \(G\) 是二分图。

判定

染色法。

枚举没有访问的点 \(x\) 开始 dfs，遍历点时用 \(0\) 和 \(1\) 两种颜色交替给节点染色。若出现一个点 \(x\) 的邻接点 \(y\) 染色过且 \(col_x = col_y\)，则出现奇环，不是二分图。

所有点染色成功，则是一张二分图。