이분 그래프 (bipartite graph)

<정의>

graph의 모든 node를 빨강과 파랑으로 색칠하되, 모든 edge가 빨강과 파랑 node를 포함해야 한다

위 그림에서 각 edge는 빨강과 초록 node를 포함하고 있으며, 같은 색의 두 node를 포함하는 edge는 존재하지 않는다

=> 같은 색의 두 node를 포함하는 edge가 존재할 경우 해당 그래프는 이분 그래프가 아니다

 

<구현>

bool isBipartite() {
    for (int i = 1; i <= v; i++) {
        for (int j = 0; j < A[i].size(); j++) {
            int next = A[i][j];
            if (visited[i] == visited[next]) return false;
        }
    }

    return true;
}

- graph를 인접 리스트로 표현한 2D vector A에 대해 이분 그래프의 여부를 판단하는 예시 코드