[BOJ1707] 이분 그래프

[BOJ1707] 이분 그래프

문제 링크

문제 설명

• 이분 그래프란 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때의 그래프를 말한다.

• 쉽게 말해서, 인접한 정점끼리는 서로 다른 색으로 칠해서 모든 정점을 두가지 색으로만 칠할 수 있는 그래프를 말한다.

• 그래프의 정점의 개수, 간선의 개수를 입력받고, 인접한 두 정점의 번호를 간선의 개수만큼 입력받는다.

• 이때 만들어진 그래프가 이분 그래프인지 판별하는 문제.

코드 리뷰

• 그래프가 애초에 두덩어리로 나눠져있는 경우를 생각못해서 계속 틀렸다.

• DFS로도 한번 풀어봐야겠다.

• BFS로는 어렵지 않게 풀수 있었다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int check[20005];

int bfs(int v, vector <vector <int>> &g) {
	queue <int> q;
	int n = 1;
	check[v] = n;
	q.push(v);
	while (!q.empty()) {
		int now = q.front();
		n = check[now];
		q.pop();
		int size = g[now].size();
		for (int i = 0; i < size; i++) {
			int next = g[now][i];
			if (check[next] == 0) {
				if (n == 1) {
					check[next] = 2;
					q.push(next);
				}
				if (n == 2) {
					check[next] = 1;
					q.push(next);
				}
			}
			else if(check[next]!=0){
				if (check[now] == check[next]) return 0;
				else if (check[now] != check[next]) continue;
			}
		}
	}
	return 1;
}

int main() {
	int k, V, E;
	scanf("%d", &k);
	for (int i = 0; i < k; i++) {
		scanf("%d%d", &V, &E);
		vector <vector <int>> g(20005);
		for (int j = 0; j < E; j++) {
			int a, b;
			scanf("%d%d", &a, &b);
			g[a].push_back(b);
			g[b].push_back(a);
		}
		int result = 0;
		for (int k = 1; k <= V; k++) {
			if (check[k] != 0) continue;
			result = bfs(k, g);
			if (result == 0) break;
		}
		if (result == 1) printf("YES\n");
		if (result == 0) printf("NO\n");
		memset(check, 0, sizeof(check));
	}
	return 0;
}