1707] 이분 그래프

문제 설명

: 입력으로 만들어진 해당 그패프가 이분 그래프이면 YES를, 아니라면 NO를 출력하는 문제 

위키백과에서 이분 그래프의 정의를 보면 다음과 같다.

그래프 이론에서, 이분 그래프(二分graph, 영어: bipartite graph)란 모든 변이 X에 있는 꼭짓점과 Y의 꼭짓점을 잇는 형태로 되도록 꼭짓점의 집합을 두 개의 부분집합 X, Y로 나눌 수 있는 그래프이다. 다르게 표현하자면, 그래프의 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 경우 이분 그래프라고 한다. 같은 말로 색칠수 χ(G)가 2이하인 경우이다.

(출처 : https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84)

그림으로 쉽게 설명해 보자면

이 그래프는 이분 그래프다. 빨간색 노드끼리는 서로 인접하지 않고, 파란색 노드 또한 그렇다.

하지만 이 경우에는 4번 노드와 5번 노드는 같은 색깔인데 연결 되어있으므로, 이분 그래프가 아니다.

그냥 간단하게 표현하면 이렇게 하나의 edge가 각기 다른 색깔의 노드를 가지면 된다.

그러면 빨간색이라는 A그룹과 파란색이라는 B그룹의 이분 그래프를 형성 할 수 있다.

이분 그래프임을 확인하는 방법은 간단하다. bfs 혹은 dfs를 통해서 탐색을 해가면서

자신과 연결된 노드에는 자신과 다른 색깔을 칠해주면 된다.

(빨간색은 0, 파란색은 1로 값을 준다고 생각하면 된다.)

그러다가 이미 색칠되어 있는 노드를 만났을 때, 자신과 같은 색깔을 가지고 있다면
이분 그래프가 아님을 바로 알 수 있게 된다.

문제링크 [1238 : 이분 그래프]

소스 코드

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;


int chk[20002];
bool bfs(vector < vector <int> >vec,int n)
{
	int a, b;
	int k = 0;
	queue <int> que;
	
	while (1)
	{
		bool flag = false;
		for (int i = 1; i <= n; i++)  // 그래프가 여러개 있을 수 있다
		{
			if (chk[i] == -1)
			{
				flag = true;
				que.push(i);
				chk[i] = 0;
				break;
			}
		}
		if (!flag)break;

		while (!que.empty())
		{
			a = que.front();
			k++;
			que.pop();
			for (int i = 0; i < vec[a].size(); i++)
			{
				b = vec[a][i];
				if (chk[b] == -1)
				{
					chk[b] = (chk[a] + 1) % 2;
					que.push(b);
				}
				else
				{
					if (a != b && chk[b] == chk[a])
						return false;
				}
			}
		}
	}

	return true;
}

int main()
{
	int t, a, b, m, n;
	scanf("%d",&t);
	while (t--)
	{
	
		scanf("%d %d", &n, &m);
		vector < vector <int> > vec(n + 3);
		for (int i = 1; i <= n+1; i++)chk[i] = -1;
		for (int i = 0; i < m; i++)
		{
			scanf("%d %d", &a, &b);
			vec[a].push_back(b);
			vec[b].push_back(a);
		}

		if (bfs(vec,n))
			printf("YES\n");
		else
			printf("NO\n");
		

	}
	return 0;
}