[BOJ] 1707 : 이분 그래프

Question

---

Solution

• 이분 그래프는 정점에 대해 두 가지의 색으로 나누었을 때 현재 노드와 인접한 노드가 서로 다른색이면 이분 그래프가 된다.
• 방문처리와 색깔처리를 한번에 할 nodeColor 배열을 선언한다. (0 ‘방문x’, 1, 2)
• 방문한 노드가 0일경우 1로 만들고, 전 노드가 1이면 2, 2면 1로 다르게 색칠한다.
• 이분 그래프 검사를 하여 도중에 인접노드와 같은 색을 띄면 중단시키고 바로 ‘NO’를 출력한다.
• 그래프가 모두 이어져있지 않을 수 있기때문에 모든 정점에 대해 dfs()를 실행한다.

---

Cord

#include <iostream>
#include <vector>
#include <string.h>

#define MAX 20001

using namespace std;

int v, e;

vector<int> graph[MAX];
int nodeColor[MAX];

// color : 0 = 방문 하지 않음
void dfs(int _node)
{	
	if (!nodeColor[_node]) { nodeColor[_node] = 1; }

	for (int i = 0; i < graph[_node].size(); i++)
	{
		int next = graph[_node][i];
		if (!nodeColor[next])
		{
			if (nodeColor[_node] == 1)
			{
				nodeColor[next] = 2;
			}
			else if (nodeColor[_node] == 2)
			{
				nodeColor[next] = 1;
			}
			dfs(next);
		}
	}
}

// 인접한 노드의 색과 같으면 "No"
string answer()
{
	for (int i = 1; i <= v; i++)
	{
		for (int j = 0; j < graph[i].size(); j++)
		{
			int next = graph[i][j];
			if (nodeColor[i] == nodeColor[next])
			{
				return "NO";
			}
		}
	}
	return "YES";
}

int main()
{
	// 케이스의 수
	int k;
	cin >> k;

	for (int idx = 0; idx < k; idx++)
	{	
		// 정점의 수, 간선의 수
		cin >> v >> e;

		// 간선 연결
		for (int i = 0; i < e; i++)
		{
			int u, v;
			cin >> u >> v;

			graph[u].push_back(v);
			graph[v].push_back(u);
		}

		// dfs 실행
		for (int i = 1; i <= v; i++)
		{
			if (!nodeColor[i])
			{
				dfs(i);
			}
		}

		// 출력
		cout << answer() << '\n';

		// 초기화
		memset(graph, 0, sizeof(graph));
		memset(nodeColor, 0, sizeof(nodeColor));
	}
	return 0;
}

---

Result

모든 정점에 대해 dfs()를 실행하지않아 실패.