백준 1707 이분 그래프 (c++) : 피너클

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

1707번: 이분 그래프

bfs를 이용해 풀었다.

이분 그래프란 무엇인가

위와 같은 그래프다. 이웃한 정점끼리는 색이 절대로 같지 않다.

위의 그래프는 1과 2가 이웃하지만 서로 색이 같으니 이분 그래프가 아니다.

int v, e;
int color[20001];
vector<int> graph[20001];

사용할 변수들이다.

color[i]는 i번째 정점에 들어있는 색이고 graph[i]는 i에 이웃한 정점을을 저장한다.

int test;
cin >> test;
while (test-- > 0) {
    memset(color, -1, sizeof(color));

test를 입력받고 while문을 돌리며 color를 전부 -1로 초기화한다.

    cin >> v >> e;
    for (int i = 0; i < e; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for (int i = 1; i <= v; i++) {
        if (color[i] == -1) bfs(i);
    }

그후 v와 e를 입력받고 e만큼 이웃하는 정점들을 입력받은뒤 graph에 넣어준다.

그후 만약 color[i]가 -1이라면 아직 방문하지 않은 정점이라는 뜻이니 bfs를 돌려준다.

void bfs(int first) {
	queue<pair<int, int>> q;
	q.push({ first, 0 });
	color[first] = 0;

bfs함수다.

queue에는 {현재 정점, 현재 정점의 색} 이 들어간다. q에 first와 0을 넣어주고 color[first] = 0으로 저장해준다.

	while (!q.empty()) {
		int now = q.front().first;
		int now_color = q.front().second;
		q.pop();

		int next_color = (now_color == 0 ? 1 : 0);
		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i];
			if (color[next] == -1) {
				color[next] = next_color;
				q.push({ next, next_color });
			}
		}
	}
}

그후엔 일반적인 bfs와 같다. 다만 특정 조건에서 while문을 빠져나가는 것이 아닌 q가 전부 빌때까지 계속해서 반복한다.

만약 이웃된 정점이 아직 color가 -1이라면 nextcolor를 넣어준뒤 queue에 넣어준다.

    if (solve()) cout << "YES" << '\n';
    else cout << "NO" << '\n';

    for (int i = 1; i <= v; i++) graph[i].clear();
}

다시 main함수로 돌아와 만약 solve를 돌렸는데 true가 반환되면 YES를 출력하고 아니면 NO를 출력한다.

그후 모든 graph를 clear로 초기화한다.

bool solve() {
	for (int now = 1; now <= v; now++) {
		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i];
			if (color[now] == color[next]) {
				return false;
			}
		}
	}
	return true;
}

solve함수다.

정점의 개수만큼 반복하며 만약 현재 정점과 이웃한 정점의 색이 같으면 바로 false를 반환하고

아니면 true를 반환한다.

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

using namespace std;

int v, e;
int color[20001];
vector<int> graph[20001];

void bfs(int first) {
	queue<pair<int, int>> q;
	q.push({ first, 0 });
	color[first] = 0;
	while (!q.empty()) {
		int now = q.front().first;
		int now_color = q.front().second;
		q.pop();

		int next_color = (now_color == 0 ? 1 : 0);
		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i];
			if (color[next] == -1) {
				color[next] = next_color;
				q.push({ next, next_color });
			}
		}
	}
}

bool solve() {
	for (int now = 1; now <= v; now++) {
		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i];
			if (color[now] == color[next]) {
				return false;
			}
		}
	}
	return true;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int test;
	cin >> test;
	while (test-- > 0) {
		memset(color, -1, sizeof(color));
		cin >> v >> e;
		for (int i = 0; i < e; i++) {
			int a, b;
			cin >> a >> b;
			graph[a].push_back(b);
			graph[b].push_back(a);
		}
		for (int i = 1; i <= v; i++) {
			if (color[i] == -1) bfs(i);
		}
		if (solve()) cout << "YES" << '\n';
		else cout << "NO" << '\n';

		for (int i = 1; i <= v; i++) graph[i].clear();
	}
}

전체코드다.