DFS, BFS 모두 사용할 수 있으나 BFS가 더 자연스럽게 할 수 있다.
정점 0으로 색칠하고 다음 정점 1로 색칠 하면서 두 가지 색깔로 색칠하면서 검사하면 된다.

Q. 정점 v개인 단순 그래프가 이분 그래프라면 최대 간선의 개수는?
A. S, T 정점 그룹으로 나눠지니, S-T 연결되는 최대 간선 SxT개

소스 코드

queue<int> q;
q.push(s);    // 시작 정점 s
int color[V];
color[s] = 0;
bool isBipartite = true;
while(!q.empty() & isBipartite){
    int u = q.front(); q.pop();
    for (int i = 0; i < adj[u].size(); ++i){
        int v = adj[u][i];
        if (color[v] == INF){  // v가 색칠 안되었으면,
            color[v] = 1 - color[u];  // {0, 1} 중 하나 색칠
            q.push(v);
        }
        else if (color[v] == color[u]){ // v가 색칠되어 있는데 u랑 같은 색이면, 충돌
            isBipartite = false;
            break;
        }
    }
}