BOJ_1707 : 이분 그래프

문제

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

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

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

bfs 로 하면 queue로 인한 메모리초과 가능성이 있으니 가급적 dfs 로 해결하자.

C++ 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
bool b = true;
void dfs(vector<vector<int> >& vertex, vector<int>& color, int index) {
	
	for (int i : vertex[index]) {
		if (color[i] == 0) {
			color[i] = -(color[index]);
			dfs(vertex, color, i);
		}
		else {
			if (color[i] != color[index]) {
				continue;
			}
			else if (color[i] == color[index]) {
				b = false;
				return;
			}
		}
	}
	
}

int main() {
	int t;
	cin >> t;

	while (t--) {
		int v, e;
		cin >> v >> e;
		vector< vector < int > > vertex(v + 1);
		vector<int> color(v + 1, 0);
		for (int i = 0; i < e; i++) {
			int x, y;
			cin >> x >> y;
			vertex[x].push_back(y);
			vertex[y].push_back(x);
		}
		b = true;
		for (int i = 1; i <= v; i++) {
			if (color[i] == 0) {
				color[i] = 1;
				dfs(vertex, color, i);
			}
			if (!b) break;
		}
		if (b) cout << "YES" << '\n';
		else cout << "NO" << '\n';
	}


	return 0;
}