백준 1707 c++ "이분 그래프" -PlusUltraCode-

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

 

 

[필자 사고]

이분 그래프가 맞냐 틀리냐를 묻는 문제이다.

 

먼저 이분 그래프의 정의를 정리하겠다.

정의 : 간선으로 연결된 인접한 두 노드는 서로 다른 색깔을 가져야 된다.

 

즉 필자는 BFS탐색을 진행하면서 기존 노드의 방문 번호가 0번이면 다음 방문 노드의 번호는 1번인 식으로

색깔을 판별했따.

 

시간복잡도를 적어보면 BFS()  => O(V+E)  20000+ 200000 => 22000 정도이고
테스트 케이스가 최대 5개이므로 10^6 정도로 추정된다. 

 

 

여기서 주의할 점은 매 테스트 케이스마다 배열 들을 초기화 해주는걸 잊지 말아야 된다.

 

 

 

[소스 코드]

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> arr;
vector<int> visited;

int K, V, E;
int resultFlag = 0;

void Input() {
	cin >> V >> E;
	arr.clear();
	visited.clear();
	arr.resize(V + 1);
	visited.resize(V + 1, -1);
	
	for (int i = 0; i < E; i++) {
		int start, end;
		cin >> start >> end;
		arr[start].push_back(end);
		arr[end].push_back(start);
	}
}


void BFS(int startIdx) {
	visited[startIdx] = 0;// 0과 1로 숫자를 방문처리한다.
	queue<int> myQueue;
	myQueue.push(startIdx);
	while (!myQueue.empty()) {
		int nowNumber = myQueue.front();
		myQueue.pop();

		for (int nextNumber : arr[nowNumber]) {
			
			if (visited[nextNumber] == -1) {
				visited[nextNumber] = (visited[nowNumber] + 1) % 2;
				myQueue.push(nextNumber);
				continue;
			}
			if (visited[nextNumber] ==visited[nowNumber] ) {
				resultFlag = 1;
				return;
			}

		}
	}
}


void GameStart() {
	cin >> K;
	for (int i = 0; i < K; i++) {
		Input();
		for (int node = 1; node <= V; node++) {
			if (resultFlag == 1) {
				cout << "NO" << '\n';
				break;
			}
			if (visited[node] == -1) {
			
				BFS(node);
			
			}
		}
		if (resultFlag == 0) {
			cout << "YES" << '\n';
		}
		resultFlag = 0;
		

	}
}

int main(void) {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	GameStart();
}