문제

https://www.acmicpc.net/problem/1707

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

참고: https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html

입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈칸을 사이에 두고 주어진다.

• 2 ≤ K ≤ 5
• 1 ≤ V ≤ 20,000
• 1 ≤ E ≤ 200,000

출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

---

풀이

참고: https://jdselectron.tistory.com/51

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility> 
#include <cstring> 
#include <queue>
#define MAX 20001 
#define RED 1
#define BLUE 2
using namespace std;

int v, e; 
vector<int> graph[MAX]; 
int colored[MAX]; 

void bfs(int start){
	queue<int> q; 
	q.push(start); 
	colored[start] = RED; 

	while(!q.empty()){ 
		int x = q.front(); 
		q.pop(); 

		// 큐에서 꺼낸 노드는 red와 blue 중에 하나 
		int color = 0; 
		if(colored[x] == RED){ 
			color = BLUE; 
		}else{
			color = RED; 
		}

		// 인접한 정점인데 아직 색상이 없는 경우, 반대되는 색상으로 칠하기 
		for(int i = 0; i < graph[x].size(); i++){
			int y = graph[x][i]; 
			if(!colored[y]){
				q.push(y); 
				colored[y] = color; 
			}
		}
	}
}

void dfs(int x){
	if(!colored[x]){ 
		colored[x] = RED; 
	}

	int color = 0; 
	if(colored[x] == RED){ 
		color = BLUE;
	}else {
		color = RED; 
	}

	for(int i = 0; i < graph[x].size(); i++){ 
		int y = graph[x][i]; 
		if(!colored[y]){ 
			colored[y] = color;
			dfs(y); 
		}
	}
}

bool isBipartite(){
	// 그래프를 순회하면서 
	// 인접한 정점이 다른 색상으로 칠해져있는지 검사 
	for(int i = 1; i <= v; i++){
		for(int j = 0; j < graph[i].size(); j++){
			int next = graph[i][j];

			// i번째 정점에 연결된 모든 정점이 서로 다른 색상이면 이분 그래프 
			// 하나라도 같은 색상이 있으면 이분 그래프 x 
			if(colored[i] == colored[next]){
				return false; 
			}
		}
	}
	return true; 
}

int main() {
	ios::sync_with_stdio(0); 
	cin.tie(0); 

	int k;
	cin >> k; 

	while(k--){
		cin >> v >> e; 

		for(int i = 0; i < e; i++){
			int x, y; 
			cin >> x >> y; 
			graph[x].push_back(y); 
			graph[y].push_back(x); 
		}

		// 1~v번까지 인접한 정점은 서로 다른 색상으로 구분한다. 
		// 한번 색칠이 된 건 스킵한다. 
		for(int i = 1; i <= v; i++){
			if(!colored[i]){
				dfs(i); 
			}
		}

		if(isBipartite()) cout << "YES\n";
		else cout << "NO\n";

		memset(graph, 0, sizeof(graph));
		memset(colored, 0, sizeof(colored));
	}

    return 0;
}