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

www.acmicpc.net/problem/1707

1707번: 이분 그래프

처음엔 그냥 두 개의 벡터를 만들어서 나누는 식으로 구현을 하려 했지만 실패했고 결국 답을 볼 수 밖에 없었다.

 

1. 큐와 간선 그래프 등을 포함해 모든 것을 테스트 케이스마다 초기화 해주기

 

2. 연결 그래프가 아닐 수도 있다는 것

 

이 두가지가 중요한 문제였다고 생각한다.

 

결국 푼 방법은 0, 1, 2 세가지의 종류로 정점들을 나눴고 이를 활용해서 풀 수 있었다.

참고: hugssy.tistory.com/231

백준 1707번: 이분 그래프 (C++)

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

bool c = true;
int k, v, e;
queue<int> q;
vector<int> edges[20001];
int visit[20001];

void bfs(int x) {
	q.push(x);
	visit[x] = 1;
	while (!q.empty()) {
		int y = q.front();
		q.pop();
		for (int i = 0; i < edges[y].size(); i++) {
			int z = edges[y][i];
			if (visit[z] != 0 && visit[y] == visit[z]) {
				c = false;
				return;
			}
			if (visit[z] > 0) {
				continue;
			}
			q.push(z);
			visit[z] = visit[y] % 2 + 1;
		}
	}
}

int main() {
	int a, b;
	cin >> k;
	while (k--) {
		cin >> v >> e;
		for (int i = 0; i < e; i++) {
			cin >> a >> b;
			edges[a].push_back(b);
			edges[b].push_back(a);
		}
		for (int i = 1; i <= v; i++) {
			if (visit[i] == 0) {
				bfs(i);
			}
			if (!c) {
				cout << "NO" << "\n";
				break;
			}
		}
		if (c) {
			cout << "YES" << "\n";
		}
		while (!q.empty()) {
			q.pop();
		}
		for (int i = 1; i <= v; i++) {
			visit[i] = 0;
			edges[i].clear();
		}
		c = true;
	}
	return 0;
}