이분 그래프 탐색 ([1707] 이분 그래프)

이분 그래프에 대해 몇 가지 알게 된 점을 정리한다.

 

• 이분 그래프는 각 노드가 두 개의 집합으로 구분되어지는 그래프이다. 이때 각 노드의 인접 노드는 같은 집합에 있으면 안된다: v1과 v2가 인접하다고 하자, v1 -> u1이라는 집합이면 v2 -> u2 집합이어야 한다는 말이다.
• 이 말을 다시 정리하면, 1번부터 N번까지의 노드가 있을 때, 1번은 빨강색으로 칠하고, 1번과 인접한 모든 노드는 다시 파랑색, 그다음 칠해지지 않은 노드부터 시작해서 빨강색, 인접 노드는 파랑색... 이런 식으로 모든 노드를 칠했을 때, 인접 노드인데 같은 색인 경우, 이분 그래프가 아니라는 말이다.
• 다음 그림이 이분 그래프의 예이다.

출처: 위키피디아

• 수학적 정의는 다음과 같다:

출처: 위키피디아

• 노드가 한 개라면 당연히 이분 그래프가 아니다.

 

이제, 이러한 점들을 정리하여 주어진 그래프가 이분 그래프인지 판별하는 문제를 풀어보았다.

 

주요 알고리즘은 다음과 같다:

bfs()로 인접한 노드를 다른 색으로 칠해주기 -> 인접한 노드 중 같은 색이 있다면 바로 "NO\n" 출력 -> 끝까지 가면 괜찮은 것이므로 "YES\n" 출력.

 

그래프는 V = 20000이어서 연결리스트 방식(vector<deque<int>>로 구현)으로 구현했다.

 

코드:

#include <iostream>
#include <queue>
#include <deque>
#include <memory.h>

using namespace std;

const int MAX = 20001;

int K, V, E;
vector<deque<int>> graph;
int visited[MAX];

void bfsColor(int start)
{
	if (visited[start]) return;
	queue<int> Q;
	Q.push(start);
	visited[start] = 1; // 첫 시작은 1로

	while (!Q.empty())
	{
		int f = Q.front();
		int color = visited[f];
		Q.pop();

		deque<int>::iterator it;
		for (it = graph[f].begin(); it < graph[f].end(); it++)
		{
			if (!visited[*it])
			{
				if (color == 1) visited[*it] = 2;
				else visited[*it] = 1;
				Q.push(*it);
			}
		}
	}
}

bool check()
{
	for (int i = 1; i <= V; i++)
	{
		deque<int>::iterator it;
		for (it = graph[i].begin(); it < graph[i].end(); it++) 
		{
			if (*it != i && visited[i] == visited[*it]) return false; // 인접하면서 같은 색인 경우
		}
	}
	return true;
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> K;
	while (K--)
	{
		memset(visited, 0, sizeof(visited));
		graph.clear();

		cin >> V >> E;
		for (int i = 0; i <= V; i++)
			graph.push_back(deque<int>());

		for (int i = 0; i < E; i++)
		{
			int a, b;
			cin >> a >> b;
			graph[a].push_back(b);
			graph[b].push_back(a);
		}
		if (V == 1) { cout << "NO\n"; continue; }

		for (int i = 1; i <= V; i++)
			bfsColor(i); // 서로 인접한 노드마다 다른 색으로 표시
		if (check()) cout << "YES\n"; // 인접한 노드 중 같은 색이면 false
		else cout << "NO\n";
	}

	return 0;
}