[Gold / 1707] 이분 그래프

문제 링크

---

🔷 분류

그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색, 이분 그래프

✒️ 문제 설명

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

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

⬅️ 입력

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

➡️ 출력

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

💻 코드 (C++)

#include <iostream>
#include <vector>
using namespace std;
#define YELLOW 1
#define PURPLE 2

void dfs(int n, const vector<vector<int>>& adj, vector<int>& color) {
	if(color[n] == 0) color[n] = YELLOW; // 첫 노드 색칠
	for(int i = 0; i < adj[n].size(); i++) {
		int next = adj[n][i];
		if(color[next] == 0) {
			color[next] = (color[n] == YELLOW) ? PURPLE : YELLOW;
			dfs(next, adj, color);
        }
	}
}

bool check(int v, const vector<vector<int>>& adj, const vector<int>& color) {
	for(int i = 1; i <= v; i++) {
		for(int j = 0; j < adj[i].size(); j++) {
			int next = adj[i][j];
			if(color[i] == color[next]) return false; 
		}
	}
	return true;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int k;
    cin >> k;
	while (k--) {
		int v, e;
		cin >> v >> e;
		vector<vector<int>> adj(v+1);
		vector<int> color(v+1, 0);
		for(int i = 0; i < e; i++) {
			int a, b;
			cin >> a >> b;
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
		for(int i = 1; i <= v; i++) {
			if(color[i] == 0) dfs(i, adj, color);
		}
		if(check(v, adj, color)) cout << "YES\n";
		else cout << "NO\n";
	} 
	return 0;
}