二分图判定

二分图的判定问题比较少见，简单来说，就是对于给定的图，判断图是否为二分图。

可以把每个节点着以黑色和白色之一，使得每条边的两个端点颜色不同，不难发现，对于一个当且仅当每个连通分量都是二分图，因此我们只考虑无向连通图。

无向图 G 为二分图的充分必要条件：G 至少有两个顶点，且其所有回路的长度均为偶数。

int n;  //节点数
vector<int> G[N];  //G[i]表示i节点邻接的点
int color[N];  //color[i]=0,1,2 代表i节点不涂颜色、涂白色、涂黑色
//假设u是遍历时的第一个结点，则color[u]已经被初始化为1或2
bool bipartite(int u){  //判断无向图是否可二分
	for(int i = 0; i < G[u].size(); i++){  //枚举结点
		int v = G[u][i];  //相邻节点
		if(color[v] == color[u])  //若两结点颜色相同，无法二分
			return false;
		if(!color[v]){  //若结点没涂颜色
			color[v] = 3 - color[u];  //改变结点颜色，使v的颜色与u的颜色对立
			if(!bipartite(v))  //若点v不满足二分图话，则无法二分
				return false;
		}
	}
	return true;
}