이분 그래프 여부
Coddy의 그래프 - 자료구조 시리즈 #9 코스 레슨 — 14개 중 14번째.
그래프의 정점들을 두 그룹으로 나누어 모든 간선이 한 그룹의 정점과 다른 그룹의 정점을 연결하도록 할 수 있다면, 그 그래프를 이분(bipartite) 그래프라고 합니다. 빨간색과 파란색을 생각해보세요. 모든 간선은 하나의 빨간색 끝점과 하나의 파란색 끝점을 가집니다.
BFS는 이를 확인하는 명확한 방법을 제공합니다. 임의의 정점에서 시작하여 빨간색으로 칠하고 밖으로 나아갑니다. 각각의 새로운 이웃은 이전 정점과 반대되는 색으로 칠해집니다. 만약 같은 색을 가진 두 정점을 연결하는 간선을 발견한다면, 그 그래프는 이분 그래프가 아닙니다. 대표적인 예외 사례는 홀수 길이의 사이클입니다. 삼각형 0-1-2-0은 정점 0이 빨간색과 파란색이 모두 되도록 강제합니다.
기억해야 할 점 하나는, 그래프에 여러 개의 연결 요소(connected components)가 있는 경우 각 요소마다 새로 2색 칠하기를 시작해야 한다는 것입니다. 가장 쉬운 패턴은 모든 정점을 순회하며 색이 칠해지지 않은 정점을 찾을 때마다 BFS를 시작하는 루프를 사용하는 것입니다.
챌린지
쉬움2차원 정수 배열 adjacency와 정수 배열 vertices를 인자로 받아, 그래프가 이분 그래프(bipartite)이면 true를, 그렇지 않으면 false를 반환하는 함수 isBipartite를 작성하세요.
그래프를 생성하세요(각각 addVertex를 호출한 후, addEdge를 호출). 그런 다음 모든 연결된 컴포넌트에 대해 BFS를 사용하여 2-색칠(2-color)을 수행합니다: 시작 색상을 0으로 할당하고, 각 이웃에게는 1 - color[u] 색상을 부여합니다. 만약 두 끝점이 이미 동일한 색상을 가진 간선을 발견하면 false를 반환하세요. 그렇지 않으면 true를 반환합니다.
반드시 Graph 클래스를 사용해야 합니다 (graph에 제공됨). 인접 관계를 모델링하기 위해 언어 내장 기능(맵, 셋 등)을 사용하지 마세요. 알고리즘을 위한 보조 데이터(색상 맵, 큐)는 표준 라이브러리 타입을 사용할 수 있습니다.
직접 해보기
#include <stdio.h>
#include "solution.h"
int main() {
int n, m;
if (scanf("%d %d", &n, &m) != 2) return 0;
int vertices[MAX_VERTICES];
for (int i = 0; i < n; i++) scanf("%d", &vertices[i]);
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
printf("%s\n", isBipartite(adjacency, m, vertices, n) ? "true" : "false");
return 0;
}