백준 1707 이분 그래프

www.acmicpc.net/problem/1707

1707번: 이분 그래프

백준 1707 이분 그래프

정답률이 꽤나 낮았는데 한번에 맞추어서 기분이 좋았던 문제이다. 백준 이분 그래프는 인접하지 않는 정점들을 두개의 그룹으로 나눌 수 있는지 판단하는 문제이다. 

 

필자의 경우 현재의 그룹이 0이면 방문한적 있는 정점의 그룹이 현재 정점의 그룹과 같다면 NO를 출력해주었다.  

오른쪽의 경우 4의 정점을 방문하고 있을 때 다음 정점의 3과 그룹이 같기 때문에 NO를 출력하게된다. 그리고 새로운 정점에 방문할 때는 현재의 정점과 반대의 정점을 저장했다. 

 

그리고 하나의 그래프 만을 검사하면 안된다. 아래와 같은 그래프가 존재할 수 있기 때문이다. 

 

이 문제는 위와 같이 여러개의 그래프가 존재할 수 있다. 

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

void solve();

int main(){
	int K;

	scanf("%d", &K);

	for(int i = 0; i < K; i++){
		solve();
	}
}

void solve(){
	vector<int> edge[20002];
	queue <pair<int, int> > qu;
	int visited[20002] = { 0, }, group[20002] = {0, };
	int V, E, start, end;

	scanf("%d %d", &V, &E);
	
	for(int i = 0; i < E; i++){
		scanf("%d %d", &start, &end);
		edge[start].push_back(end);
		edge[end].push_back(start);
	}

	for(int i = 0; i < V; i++){
		if(visited[i] == 0){
			qu.push(make_pair(i, 0));
			while(!qu.empty()){
				pair<int, int> now = qu.front();
				int nowVertex = now.first;
				int nowGroup = now.second;
				group[nowVertex] = nowGroup;
				visited[nowVertex] = 1;
				qu.pop();
				for(auto next : edge[nowVertex]){
					if(visited[next] == 0){
						qu.push(make_pair(next, nowGroup == 0? 1 : 0));
					}else{
						if(nowGroup == group[next]){
							printf("NO\n");
							return ;
						}
					}
				}
			}
		}
	}
	printf("YES\n");
}