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

https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

위키백과:

그래프 이론에서, 이분 그래프(二分graph, 영어: bipartite graph)란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다.

 

이 외에도 홀수개의 사이클이 없어야 한다는데 이게 이해가 잘 안됐었는데 그림으로 다시 확인해보면

 

홀수 사이클에선 파랑 - 파랑 으로 같은 색끼리 연결이 될 수 밖에 없기 때문에 이분 그래프가 아니다.

 

DFS나 BFS를 통해 색을 칠하며 정점을 탐색하는 것이 중요한 문제였다.

코드에서는 DFS에서 탐색을 하면서, 이분 그래프 여부도 같이 체크해줬다.

 

color는 방문전에는 0으로 시작하고, 탐색 시 color % 2 + 1 을 통해 색을 반전시켜줬다.

color = 1인 경우 1 % 2 + 1 = 2

color = 2인 경우 2 % 2 + 1 = 1

 

memset도 필요한 부분까지만 리셋해주며 코드를 좀 더렵혀봤다.

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int color[20001];
bool isBipartiteGraph;

void DFS(vector<vector<int>>& list, int current, int nextColor)
{
	int size = list[current].size();

	for (int i = 0; i < size; ++i)
	{
		if (!isBipartiteGraph)
		{
			return;
		}

		int next = list[current][i];

		if (color[next] == 0)
		{
			color[next] = nextColor;
			DFS(list, next, nextColor % 2 + 1);
		}
		else if (color[current] == color[next])
		{
			isBipartiteGraph = false;
			return;
		}
	}
}

int main()
{
	int testCase;
	int v, e;
	int from, to;

	cin.tie(0);
	cin >> testCase;

	while (testCase--)
	{
		vector<vector<int>> list;
		isBipartiteGraph = true;

		cin >> v >> e;

		list.resize(v + 1);
		memset(color, 0, sizeof(int) * (v + 1));

		for (int i = 0; i < e; ++i)
		{
			cin >> from >> to;

			list[from].push_back(to);
			list[to].push_back(from);
		}

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

			DFS(list, i, color[i] % 2 + 1);
		}

		if (isBipartiteGraph)
		{
			cout << "YES" << endl;
		}
		else
		{
			cout << "NO" << endl;
		}
	}
}