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

 

1) 문제설명

백준 Online Judge 1707번 이분 그래프

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

1707번: 이분 그래프

 

2) 아이디어

이분 그래프는 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지의 색으로 칠할 수 있는 그래프를 말한다.

이분 그래프를 구현하기 위해서 bfs를 사용하고 bfs로 정점들을 방문하되 번갈아 가면서 색을 칠해준다. visited배열에 red는 1로 blue는 2로 인접한 정점을 방문하면서 저장하였다.

이후 정점들을 차례로 방문하면서 인접한 정점이 색이 같다면 NO를 출력하고 전부 방문했을 때 색이 달랐다면 YES를 출력한다.

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

// 이분 그래프 : bfs or dfs 방문하되 방문 값을 1,2 로 번갈아가면서 놓는다.
using namespace std;
vector<int> graph[20001];
int visited[1000001];
void bfs(int x) {
	int color = 1; // red = 1, blue = 2
	queue<int> q;
	q.push(x);
	visited[x] = color; // 처음 방문 한 곳은 red
	

	while (!q.empty()) {
		x = q.front();
		q.pop();
		if (visited[x] == 1) { // 전에 red를 방문 했다면 다음은 blue로 해야하기 때문에 color를 2로 놓는다.
			color = 2;
		}
		else if (visited[x] == 2) { // 전에 blue를 방문 했다면 red로 해야하기 때문에 color를 1로 놓는다.
			color = 1;
		}

		for (int i = 0; i < graph[x].size(); i++) {
			int temp = graph[x][i];
			if (!visited[temp]) {
				q.push(temp);
				visited[temp] = color;
			}
			
		}
	}
}

int check(int v) {
	for (int i = 1; i <= v; i++) {
		for (int j = 0; j < graph[i].size(); j++) {
			int temp = graph[i][j];
			if (visited[i] == visited[temp]) {
				return 0;
			}
		}
	}
	return 1;
}
int main() {
	int k;
	cin >> k;
	for (int i = 1; i <= k; i++) {
		int v, e;
		cin >> v >> e;
		for (int j = 1; j <= e; j++) {
			int a, b;
			cin >> a >> b;
			graph[a].push_back(b);
			graph[b].push_back(a);
		}

		for (int i = 1; i <= v; i++) {
			if (!visited[i]) { // 방문하지 않았다면 
				bfs(i);// bfs순회
			}
		}

		if (check(v) == 1) {
			cout << "YES" << endl;
		}
		else {
			cout << "NO" << endl;
		}

		for (int i = 0; i <= v; i++) {
			graph[i].clear();
		}
		memset(visited, false, sizeof(visited));
	}
	

}