그래프의 노드를 두 집합으로 나누었을 때, 집합의 노드들 사이는 간선으로 연결되지 않고 오직 서로 다른 집합의 노드들과 연결된 그래프를 말한다. 즉 같은 그룹 내의 노드들 사이에서는 간선이 없다. 또한 도형의 변으로 생각했을 때, 간선을 제거하면 한쪽은 무조건 빨간색, 다른 쪽은 파란색과 같이 선의 각 끝점의 집합이 달라야 한다.
위 그림을 보면 빨간색 노드와 파란색 노드로 나뉘어져 있고 빨간색 끼리는 서로 연결되지 않았고, 파란색 역시도 서로 연결되지 않았다..만약 파란색끼리 혹은 빨간색 끼리 연결되었다면 이는 더 이상 이분 그래프가 아니다. 또한 만약 연결된 것이 없는 즉, 간선이 없는 노드가 있다면 어떠한 집합에도 속하지 않기 때문에 이분 그래프의 정의와 맞지 않기 때문에 이분 그래프가 아니다. 보통 BFS, DFS로 이분 그래프를 확인할 수 있다.
백준 1707번 문제로 이를 확인해 볼 수 있다.
1. 처음 노드의 집합을 임의의 집합으로 하나 설정한다.
2. 이를 큐에 삽입하고, 삽입된 노드와 인접한 노드들을 모두 탐색해 처음 집합과 다른 집합으로 설정한다.
3. 만약 인접한 노드가 같은 집합이라면 이분 그래프가 아니기 때문에 실패
4. 이를 반복한다.
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
vector<int> graph[200001];
int visited[200001];
bool bfs(int start) {
queue<int> q;
visited[start] = 1; // 처음 집합을 1로 설정한다.
q.push(start);
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = 0; i < graph[x].size(); i++) {
int y = graph[x][i];
if (!visited[y]) {
// 1을 빼면 2가 되고 2를 빼면 1이 된다.
visited[y] = 3 - visited[x];
q.push(y);
}
//만약 현재 노드와 지금 탐색하는 노드의 집합이 같다면 실패
else if (visited[y] == visited[x])
return false;
}
}
return true;
}
int main() {
int k, v, e, a, b;
cin >> k;
while (k--) {
cin >> v >> e;
for (int i = 1; i <= v; i++) {
graph[i].clear();
visited[i] = 0;
}
for (int i = 0; i < e; i++) {
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
bool isBipartite = true;
// 노드를 전부 탐색한다.
for (int i = 1; i <= v; i++)
if (visited[i] == 0)
if (bfs(i)==false) {//인접한 두 노드의 집합이 같다면
isBipartite = false;// 실패
break;
}
if (isBipartite)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}
