Bipartite graph(이분그래프)(백준 1707)

Bipartite Graph

다음과 같은 성질을 가질 때 그 그래프는 Bipartite하다고 할 수 있다.

전체 vertex를 v1과 v2로 나누었을 때

 -> v1노드끼리는 edge가 없음

 

 -> v2노드끼리는 edge가 없음

 

-> v1과 v2와의 edge는 존재한다.

v ∈ v1 , w ∈ v2 , (v,w) ∉ E

위의 그림에서 같은 집합의 노드끼리는 edge가 없는것을 쉽게 확인할 수 있다.

예를들어 다음과 같은 ring 형식의 그래프는

vertex가 홀수일 때는 Bipartite가 아니지만 , 짝수일 때는 Bipartite임을 알 수 있다.

이렇게 그래프가 Bipartite한지 아닌지는 DFS를 통해서도 판별할 수 있다.

다음의 문제를 통해 확인해보자.

확인을 위해 int check[]라는 배열을 두었고

값이 0일때는 탐색 안됨, 1일 떄는 첫번째 집합, 2일 떄는 두번째 집합에 속한것으로 하기로 했다.

DFS를 통해 탐색할 때 처음 탐색하는 노트는 1을 주었고 다음 탐색하는 노드부터는

현재 노드와 다른 숫자를 주는식으로 탐색을 진행하였다.

다음 노드가 이미 탐색된 노드이면서 현재노드와 같은 집합에 속할 때

bool 자료형에 따로 그 결과를 저장하여 bipartite인지 아닌지에 대해 출력 가능하도록 하였다.

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

vector<int> arr[20001];
int check[20001]; //vertex의 상태 저장
bool b;//bipartite인지 아닌지 저장
void DFS(int start) {
	for (int i = 0; i < arr[start].size(); i++) {
		int next = arr[start][i];
		if (check[next] != 0) { //다음 노드가 이미 탐색된 노드일 때
			if (check[start] == check[next]) {//소속된 집합이 같다면
				b = false; return;//bipartite가 아니다.
			}
		}
		else {//다음 노드가 탐색이 안된 상태일 때
			if (check[start] == 1) { //현재 노드가 집합1에 속한다면
				check[next] = 2;//다음 노드는 집합2에 속하게 한다.
				DFS(next);
			}
			else { //현재 노드가 집합2에 속한다면
				check[next] = 1;//다음 노드는 집합 1에 속하도록 한다.
				DFS(next);
			}
		}
	}
}

int main()
{
	int K;
	int V; long long E;
	int x, y;
	scanf("%d", &K);
	while (K--) {
		memset(check, 0, sizeof(int) * 20001);
		b = true;
		scanf("%d %lld", &V, &E);
		while (E--) {
			scanf("%d %d", &x, &y);
			arr[x].push_back(y);
			arr[y].push_back(x);
		}
		for (int i = 1; i <= V; i++) {
			if (check[i] == 0) {
				check[i] = 1;
				DFS(i);
			}
			if (b == false) break;
		}
		b ? printf("YES\n") : printf("NO\n");
		for (int i = 1; i <= V; i++)
			arr[i].clear();
	}
	
}