18) 백준 1707 - 이분 그래프

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

1707번: 이분 그래프

---

뻘짓해서 좀 걸렸던 문제..

#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 : 탐색을 했고 번호 부여해서 근접한 Vertex가 다른가를 체크

 

중요한 점은 그래프가 전혀 이어지지 않은 것도 체크하기 위해서 check 배열을 하나하나 체크해가며 0이 있으면 dfs를 실행했다. 또한 떨어진 두 그래프가 있을때 첫번째 그래프에서 이미 이분 그래프가 아닌경우를 위해 flag로 확인 해주고 

flag가 0인 경우에는 dfs를 더 할 필요가 없다.  

 

헤맨 이유는 초기화를 계속 이상하게 했기 때문....

2차 벡터를 초기화 하는 과정에서 for문에 i <= V 를 i < V 로적어두고 눈치를 못챘었다..ㅠㅠ 

으휴으휴....

 

( 혹시나 6%에서 틀렸으면 초기화를 확인해보자. )