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

---

문제 링크: https://www.acmicpc.net/problem/1707

---

문제

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

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

---

입력

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

---

출력

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

---

내 풀이

처음 임의의 한 노드를 A로 표현하고, 그 노드와 인접한 노드를 B로 구분하는 방식을 반복해서 해당 그래프가 이분 그래프인지 확인한다.

---

코드

#include <iostream>
#include <vector>
#include <queue>
#define len 20001

using namespace std;

int K, V, E, a, b, check;
vector<int> graph[len];
queue<int>	que;
int color[len], visit[len];

int BFS(int n) {
	que.push(n);

	int a;
	while (que.size() != 0) {
		a = que.front();	que.pop();	visit[a] = 1;
		for (int t = 0; t < graph[a].size(); t++) {
			if (visit[graph[a][t]] == 0) {
				if (color[graph[a][t]] == color[a])	return 1;
				else {

					color[graph[a][t]] = 3 - color[a];
					if (visit[graph[a][t]] == 0) {
						que.push(graph[a][t]);
					}
				}
			}
		}
	}

	return 0;
}

int main() {
	scanf("%d", &K);

	for (int k = 0; k < K; k++) {
		scanf("%d %d", &V, &E);

		for (int e = 0; e < E; e++) {
			scanf("%d %d", &a, &b);

			graph[a].push_back(b);	graph[b].push_back(a);
		}

		check = 0;
		for (int v = 1; v <= V; v++) {
			if (color[v] == 0) {
				color[v] = 1;
				if (BFS(v) == 1) {
					check = 1;
					printf("NO\n");
					break;
				}
			}
		}

		if (check == 0)	printf("YES\n");

		for (int v = 1; v <= V; v++) {
			graph[v].clear();
			color[v] = 0;
			visit[v] = 0;
		}

		while (!que.empty()) que.pop();

	}

	return 0;
}