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

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

1707번: 이분 그래프

백준 1707번 이분 그래프를 풀어봤습니다.

graph의 첫 좌표는 본인입니다. 예를 들어 graph[2][0]은 (2,0)으로, graph[3][0]은 (3,0)으로 초기화 됩니다.

그 다음엔 인풋이 양방향 간선이라 하나는 정방향, 하나는 역방향으로 총 두번 넣었습니다.

테스트 케이스별로 꼭 큐와 배열들을 초기화 해줘야 합니다. 맞았는데 왜 틀렸는지 찾는 경우가 사라집니다.

 

BFS함수의 for문이 1부터 시작하는 이유는 첫 번째 좌표는 본인이기 때문입니다.

첫 번째 if문은 만약 방문했던 정점이라면 해당 정점의 상태를 가져와서 사용하는 용도입니다.

두 번째 if문은 만약 다음 정점의 상태가 결정되지 않았으면 현재 정점과 반대의 상태로 초기화 시켜줍니다.

만약 다음 정점의 상태가 현재 정점의 상태와 같다면 이분 그래프가 될 수 없습니다. false를 반환합니다.

 

BFS를 완료해도 방문하지 않은 정점이 있을 수 있습니다. 그래서 방문하지 않은 정점을 찾아서 큐에 넣어주고 다시 BFS를 실행시켜야 합니다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
using namespace std;
	
int k, v, e;

vector<pair<int, int>> graph[200001];
queue<pair<int, int>> q;
bool visited[200001];

bool BFS() {

	while (!q.empty()) {
		int x = q.front().first;
		int state = q.front().second;
		visited[x] = 1;
		q.pop();

		for (int i = 1; i < graph[x].size(); i++) {

			int next_x = graph[x][i].first;
			int next_state = graph[x][i].second;

			if (visited[next_x] == 1) {
				graph[x][i].second = graph[next_x][0].second;
				next_state = graph[x][i].second;
			}

			// If next state does not determine
			if (next_state == 0) {
				next_state = state * (-1);

				graph[x][i].second = next_state;
				graph[next_x][0].second = next_state;

				visited[next_x] = 1;
				q.push({ next_x,next_state });
			}
			else if (next_state != 0) {
				if (state == next_state) {
					return false;
				}
			}
		}
	}

	for (int i = 0; i < v; i++) {
		if (visited[i + 1] == 0) {
			q.push({ i + 1,1 });
			return BFS();
		}
	}

	return true;
}

int main() {
	cin >> k;
	int sol[5];
	int cnt = 0;
	for(int t=0;t<k;t++){
		cin >> v >> e;

		// State init
		for (int i = 0; i < v; i++) {
			graph[i + 1].push_back({ i + 1,0 });
		}
		
		// Two-way edge
		for (int i = 0; i < e; i++) {
			int a, b;
			cin >> a >> b;
			graph[a].push_back({ b,0 });
			graph[b].push_back({ a,0 });
		}

		// Push({1,1})
		graph[1][0].second = 1;
		q.push({ graph[1][0].first, graph[1][0].second });	

		sol[cnt] = BFS();

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

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

		cnt++;
	}

	for (int i = 0; i < k; i++) {
		if (sol[i])
			cout << "YES\n";
		else
			cout << "NO\n";
	}

	return 0;
}