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

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

문제

---

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

 

입력

---

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다. 

출력

---

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

 

제한

---

• 2 ≤ K ≤ 5
• 1 ≤ V ≤ 20,000
• 1 ≤ E ≤ 200,000

문제 풀이

---

그래프 탐색 문제.

이분 그래프는 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다. 즉, 한 노드의 색깔이 빨간색이면, 그와 인접한 모든 노드는 파란색이고, 한 노드의 색깔이 파란색이면 그와 인접한 모든 노드는 빨간색이어야 한다.

bfs나 dfs를 통해 노드를 탐색하며 각 노드에 색깔을 부여하거나, 체크한다. 처음 탐색을 시작할 때 시작점에 빨강과 파랑 아무 색깔이나 색깔을 부여한다. 이후 bfs의 경우 큐, dfs의 경우 스택의 front/top에 해당하는 노드와 인접한 노드들을 탐색한다. 인접한 노드를 탐색한 적이 없다면 해당 노드들에 front/top에 해당하는 노드의 색깔에 따라 반대편 색깔을 부여한다. 이후 방문여부에 체크하고 큐/스택에 넣는다. 인접한 노드들 중에 이미 탐색한 노드가 있다면 해당 노드와 front/top에 해당하는 노드의 색깔이 다른지 확인한다. 만약 두 노드의 색깔이 같다면 해당 그래프는 이분 그래프가 될 수 없다.

 

문제에서 모든 노드가 연결되어있다고 주어지지 않았으므로, 노드의 일부끼리 연결되어 있을 가능성이 있다. 이에 따라 모든 노드들을 방문하며 탐색한 노드인지 확인하고, 탐색하지 않았다면 해당 노드를 시작점으로 bfs/dfs 탐색을 진행해야 한다.

 

아래는 코드.

#include <iostream>
#include <vector>
#include <utility>
#include <queue>
using namespace std;
vector<int>* nodes;
pair<bool, char>* isVisited;
queue<int> bfsQueue;

int V, E;
bool isBipartiteGraph;

void bfs(int startNode)
{
	isVisited[startNode].first = true;
	isVisited[startNode].second = 'R';
	bfsQueue.push(startNode);
	while (!bfsQueue.empty())
	{
		if (isBipartiteGraph == false)
		{
			break;
		}
		int current = bfsQueue.front();
		for (int i = 0; i < nodes[current].size(); i++)
		{
			int nextNode = nodes[current].at(i);
			if (isVisited[nextNode].first == true)
			{
				if (isVisited[current].second == isVisited[nextNode].second)
				{
					isBipartiteGraph = false;
					break;
				}
			}
			else
			{
				if (isVisited[current].second == 'R')
				{
					isVisited[nextNode].second = 'B';
				}
				else
				{
					isVisited[nextNode].second = 'R';
				}
				isVisited[nextNode].first = true;
				bfsQueue.push(nextNode);
			}
		}
		bfsQueue.pop();
	}
}

void checkisBipartiteGraph()
{
	if (isBipartiteGraph == false)
	{
		cout << "NO" << "\n";
	}
	else
	{
		cout << "YES" << "\n";
	}
}

void reset()
{
	for (int i = 1; i <= V; i++)
	{
		nodes[i].clear();
		isVisited[i] = pair(false, '\0');
	}
	while (!bfsQueue.empty())
	{
		bfsQueue.pop();
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int T;
	cin >> T;
	for (int t = 0; t < T; t++)
	{
		int a, b;
		cin >> V >> E;
		nodes = new vector<int>[20001];
		isVisited = new pair<bool, char>[200001];
		for (int i = 1; i <= V; i++)
		{
			isVisited[i] = pair(false, '\0');
		}
		for (int i = 0; i < E; i++)
		{
			cin >> a >> b;
			nodes[a].push_back(b);
			nodes[b].push_back(a);
		}
		isBipartiteGraph = true;
		for (int nodeNum = 1; nodeNum <= V; nodeNum++)
		{
			if (isVisited[nodeNum].first == false)
			{
				bfs(nodeNum);
			}
		}
		checkisBipartiteGraph();
		reset();
	}
	return 0;
}