이분그래프 (bipartite graph)

<추가예정>

 

어떤 그래프의 모든 노드를 두가지 색 중 하나로 칠하되, 이웃 노드의 색이 모두 다르게 만들 수 있다면 그 그래프는 이분그래프이다.

 

홀수개의 간선으로 이뤄진 사이클이 없으면 이분그래프이다!

 

<이분그래프 검출 코드>

void dfs(int u, int p) {
	vst[u] = vst[p]==1?2:1;

	for (int v : adj[u]) {
		if (v == p) continue;
		if (vst[v] && !fin[v] && vst[v]==vst[u]) isNotBipartite = true;
		else if (!vst[v]) dfs(v, u);
	}

	fin[u] = true;
}