18) 백준 1707 – 이분 그래프

1707호: 이분 그래프(acmicpc.net)

한동안 고민하던 문제…

#include <bits/stdc++.h>

using namespace std;

int check(20001);
int flag; // 0 : NO , 1 : YES

vector<vector<int> > graph(20001);

// div : 1 or 2 
void dfs(int vertex, int div) {
	if(flag == 0) {
		return;
	}
	int size = graph(vertex).size();
	check(vertex) = div;
	for(int i = 0; i < size; i++) {
		if(check(graph(vertex)(i)) == 0) {
			if(div == 1) {
				dfs(graph(vertex)(i), 2);
			}
			else {
				dfs(graph(vertex)(i), 1);
			}
		}
		else if(check(graph(vertex)(i)) == div) {
			flag = 0;
			return;
		}
	}
}

int main(void) {
	int K, V, E;
	
	cin >> K;
	
	for(int i = 0; i < K; i++) {
		fill_n(check, 20001, 0);
		flag = 1;
		cin >> V >> E;
		
		for(int j = 1; j <= V; j++) {
			graph(j).clear();
		}
		
		for(int j = 0; j < E; j++) {
			int first, second;
			cin >> first >> second;
			graph(first).push_back(second);
			graph(second).push_back(first);
		}
		
		for(int j = 1; j <= V; j++) {
			if(check(j) == 0 && flag == 1) {
				dfs(j, 1);
			}
		}
		
		if(flag == 1 || V == 1) {
			cout << "YES" << endl;
		}
		else {
			cout << "NO" << endl;
		}
		
	}
}

문제는 간단해 보인다.

DFS와 BFS로 할 수 있다고 하는데 저는 DFS로 했습니다.

check라는 배열에 0, 1, 2를 넣었는데 각각 의미가 다릅니다.

0 : 아직 검색되지 않음.

1, 2: 인접한 정점이 다른지 확인하기 위해 검색하여 번호를 부여했습니다.

중요한 점은 그래프가 전혀 연결되어 있지 않은지 확인하기 위해서는 check array를 하나씩 확인하면서 0이 있으면 dfs를 실행한다는 것이다. 또한 두 개의 분리된 그래프가 있을 때 첫 번째 그래프는 이분 그래프가 아닌 경우 플래그로 확인합니다.

플래그가 0이면 추가 dfs를 수행할 필요가 없습니다.

제가 길을 잃은 이유는 초기화를 계속 이상하게 해서…

보조 벡터를 초기화하는 과정에서 for 문은 나는 <= V 깁스 나는 < V 적어놨는데..몰랐네요..

어…

(6%에서 틀리면 초기화를 확인하세요.)