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

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

1707번: 이분 그래프

 

이분 그래프라는 것을 처음 들어봤다. 두 집합으로 나누었을때 연결된 노드 끼리는 다른 집합에 속하는 것을 이분그래프라고 한다. 문제에서는 두 집합으로 나눈다고 하였는데 이것을 연결된 노드와 다른 색깔로 칠하는 것으로 표현할 수 있다.

사진 출처https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html

1번 노드부터해서 각 노드를 bfs로 방문해준다. 각 노드에서 연결된 다른 노드들을 다른 색깔로 칠한다.

모든 노드를 방문하였으면 check함수를 통해서 인접한 노드끼리 다른 색깔인지 확인한다.

시행착오:

1. 1번노드에서 bfs를 한번 수행하면 모든 노드를 방문할 수 있을 것이라고 생각 했는데 빠짐없이 방문하려면 for문을 통해서 모든 노드에 방문해야했다.

2. while문에 돌때마다 레벨이 번갈아 가면서 바뀔 것이라고  생각해서
c = ((c + 1) % 3 + (c + 1) / 3);//1-> 2 ,  2->1

로 while 문 시작할때마다 red->blue , blue->red로 바꾸어 주었는데 

매번 레벨이 바뀌지 않기 때문에

현재 노드색깔에 따라 인접 노드를 칠해주는 것으로 바꾸었다.

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

using namespace std;
int k, v, e;
vector<int>graph[20001];

char arr[20001]; //0 : 방문 x, 1: Red, 2:Blue
int a, b;

void bfs(int n)
{
	queue<int>node;
	node.push(n);
	int c = 1;
	arr[n] = 1;
	while (!node.empty())
	{
		int t = node.front();
		node.pop();
		//c = ((c + 1) % 3 + (c + 1) / 3);//1-> 2 ,  2->1
		for (int i = 0; i < graph[t].size(); i++)
		{
			if (arr[graph[t][i]] == 0)
			{
				node.push(graph[t][i]);
				if(arr[t]==1)
					arr[graph[t][i]] = 2;
				else if(arr[t]==2)
					arr[graph[t][i]] = 1;
			}
			
		}
		
	}
	
}

bool check()
{
	for (int i = 1; i <= v; i++)
	{
		for (int j = 0; j < graph[i].size(); j++)
		{
			if (arr[i] == arr[graph[i][j]])
				return false;
		}
	}
	return true;
}
int main()
{
	cin >> k;
	while (k--)
	{
		cin >> v >> e;
		for (int i = 0; i < e; i++)
		{
			cin >> a >> b;
			graph[a].push_back(b);
			graph[b].push_back(a);

		}
		memset(arr, 0, sizeof(arr));
		for (int i = 1; i <= v; i++)
		{
			if(arr[i]==0)
				bfs(i);
		}
		if (check())
			cout << "YES\n";
		else
			cout << "NO\n";
		memset(graph, 0, sizeof(graph));
		
		
	}
}