[C++] 백준 1707번 이분 그래프

DFS, BFS 문제입니다.

주어진 그래프가 이분그래프인지 아닌지 확인하는 문제입니다.
이분그래프는 각 정점에 빨강과 초록을 대입하면 알기 쉽습니다.

이웃하는 정점이 같은 색이 아닐 경우 이분그래프라 할 수 있습니다.

 

검정색 정점의 경우 이웃하는 그래프가 빨강과 초록이므로 어떤 색도 올 수 없습니다.
이와 같은경우 이분그래프가 아닙니다.

DFS를 통해 색이 칠해져있지 않다면 (color == 0) 색을 넣어줍니다. 
그리고 다음 위치에서는 전의 위치의 색을 파라미터로 보내서 다른 색으로 배치하게 합니다.

이를 반복하고
다음 탐색위치가 현재 위치의 색과 다르게 전부 칠하면 성공이며
색이 다른경우가 있다면 실패를 의미합니다.

 

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

int n;
int success;
vector<int> vec[20010];
int color[20010];

void DFS(int a, int x)
{
	if (success != 0) {
		return;
	}

	if ((color[a] == 1 && x == 1) || (color[a] == 2 && x == 2)) {
		success = -1;
		return;
	}
	else if (color[a] != 0) {
		return;
	}

	if (x == 2) {
		color[a] = 1;
		x = 1;
	}
	else if(x == 1) {
		color[a] = 2;
		x = 2;
	}

	for (int i = 0; i < vec[a].size(); ++i) {
		DFS(vec[a].at(i), x);
	}
}

int main(int argc, char *argv[])
{
	int v, e;
	int testcase;

	cin >> testcase;

	while (testcase--) {
		success = 0;

		cin >> v;
		cin >> e;

		for (int i = 1; i <= 20000; ++i) {
			vec[i].clear();
		}

		memset(color, 0, sizeof(color));

		for (int i = 0; i < e; ++i) {
			int a, b;

			cin >> a;
			cin >> b;

			vec[a].push_back(b);
			vec[b].push_back(a);
		}

		for (int i = 1; i <= v; ++i) {
			if (color[i] != 0) {
				continue;
			}

			DFS(i, 2);
		}

		if (success == -1) {
			cout << "NO" << endl;
		}
		else {
			cout << "YES" << endl;
		}
	}

	return 0;
}