백준 [1707] 이분 그래프 (bfs)

 

 

같은 레벨의 정점끼린 같은 색, 인접 노드 끼리는 다른 색을 칠한다.

만약, 인접 노드가 자신과 같은 색이라면 이분 그래프가 아니다.

예를 들면, 정점이 4개인 임의의 그래프가 있다면, 칠하는 방식은 다음과 같다.

(하얀색, 검은색)

 

하지만, 자신과 인접한 노드가 자기와 같은 색이 된다면

이분 그래프라 할 수 없다.

 

아래 그래프에서 3과 4가 연결 됐을 때,

3을 탐색 할 때, 인접 노드인 4를 검은색으로 칠해야 하는데,

4는 인접 노드인 3과 같은 하얀색이기 때문에, 이분 그래프라 할 수 없다.

반대로, 4부터 탐색한다 해도, 같은 문제가 발생한다.

 

3, 4가 연결되지 않았다면, 이분 그래프가 됐다.

 

여기서 주의할 점은, 주어진 입력이 비연결 그래프일 수 있기 때문에,

V범위 전부를 탐색해야 한다.

 

따라서 시간 복잡도는 O(V + E)가 나온다.

 

 

bfs 코드

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

int bfs(vector<vector<int>>& v)
{
	int i, j, vSize = v.size();
	int here, there, paint = 1;
	int color[20001];
	queue<int> q;
	memset(color, -1, sizeof(color));
	for (i = 0; i < vSize; i++)
	{
		// 색칠된 정점이거나, 연결된 정점이 없으면 넘어감
		if (v[i].size() == 0 || color[i] != -1)
			continue;
		else
		{
			q.push(i);
			color[i] = paint;
		}
		while (!q.empty())
		{
			here = q.front();
			q.pop();
			for (j = 0; j < v[here].size(); j++)
			{
				there = v[here][j];
				// 색칠 안 된 정점이면 칠함
				if (color[there] == -1)
				{
					q.push(there);
					color[there] = !color[here];
				}
				// 색칠된 정점인 경우, 현재 위치의 색과 같은지 확인
				else if (color[there] == color[here])
					return 0;
			}
		}
	}
	return 1;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int K, V, E, i;
	int a, b;
	cin >> K;
	while (K--)
	{
		cin >> V >> E;
		vector<vector<int>> v(V + 1);
		for (i = 0; i < E; i++)
		{
			cin >> a >> b;
			v[a].push_back(b);
			v[b].push_back(a);
		}
		if (bfs(v))
			cout << "YES\n";
		else
			cout << "NO\n";
	}
	return 0;
}