그래프가 이분 그래프인지 확인하기¶
이분 그래프란 정점들을 서로소인 두 집합으로 나누어 모든 간선이 서로 다른 집합에 속한 두 정점을 연결하도록 할 수 있는 그래프입니다(즉, 같은 집합에 속한 정점끼리 연결하는 간선이 없습니다). 이러한 집합들을 보통 쪽(side)이라고 부릅니다.
무방향 그래프가 주어집니다. 이 그래프가 이분 그래프인지 확인하고, 그렇다면 각 쪽을 출력하십시오.
알고리즘¶
그래프가 이분 그래프일 필요충분조건은 그래프의 모든 사이클의 길이가 짝수인 것이라는 정리가 있습니다. 그러나 실제로는 정의를 다르게 표현한 것을 사용하는 편이 더 편리합니다. 그래프가 이분 그래프일 필요충분조건은 그래프를 두 가지 색으로 칠할 수 있는 것입니다.
아직 방문하지 않은 각 정점에서 시작하는 일련의 너비 우선 탐색을 사용합시다. 각 탐색에서 시작 정점을 1번 쪽에 배정합니다. 한쪽에 배정된 정점의 아직 방문하지 않은 이웃을 방문할 때마다, 그 이웃을 다른 쪽에 배정합니다. 한쪽에 배정된 정점의 이웃 중 이미 방문한 정점으로 가려고 할 때는, 그 정점이 다른 쪽에 배정되어 있는지 확인합니다. 같은 쪽에 배정되어 있다면 그래프가 이분 그래프가 아니라고 결론짓습니다. 모든 정점을 방문하고 각 정점을 성공적으로 어느 한쪽에 배정했다면, 그래프가 이분 그래프임을 알 수 있으며 그 분할도 구성한 것입니다.
구현¶
int n;
vector<vector<int>> adj;
vector<int> side(n, -1);
bool is_bipartite = true;
queue<int> q;
for (int st = 0; st < n; ++st) {
if (side[st] == -1) {
q.push(st);
side[st] = 0;
while (!q.empty()) {
int v = q.front();
q.pop();
for (int u : adj[v]) {
if (side[u] == -1) {
side[u] = side[v] ^ 1;
q.push(u);
} else {
is_bipartite &= side[u] != side[v];
}
}
}
}
}
cout << (is_bipartite ? "YES" : "NO") << endl;