[C++] 이분 그래프(Bigraph)

1. 이분 그래프 (Bipartite Graph)

: 인접한 정점끼리 서로 다른 색으로 칠하여 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프

: 이때, 모든 사이클의 길이는 짝수이다

( ⇔ odd length cycle은 존재하지 않는다 )

출처 : https://www.ksakosmos.com/post/%EA%B7%B8%EB%9E%98%ED%94%84-%EC%9D%B4%EB%A1%A0-%EB%A7%9B%EB%B3%B4%EA%B8%B0-%EC%9D%B4%EB%B6%84-%EA%B7%B8%EB%9E%98%ED%94%84

 

1-1. 그래프 이론

If a graph has no odd cycle then it must be bigraph.

 

 

2. 이분 그래프 알고리즘 문제  

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

1707번: 이분 그래프

 

2-1. 알고리즘 동작 과정

• 초기 방문 노드는 RED로 설정
• 방문 노드에 대한 인접 노드를 저장한 배열 순회하며 인접 노드를 아직 방문하지 않은 상태라면 방문 노드와 다른 색상(RED or BLUE)로 설정하고 그 인접 노드에 대해 DFS 수행
• 모든 노드에 대해 DFS 수행한 후 인접 노드들끼리 색상이 같은 경우가 있다면 바로 FALSE를 반환하여 bigraph가 아님을 판단

#include <iostream>
#include <vector>
#include <stdbool.h>
#include <memory.h>
#define MAX_SIZE 20001
#define RED 0
#define BLUE 1
using namespace std;

void DFS(vector<int> (&vt)[MAX_SIZE], int* visited, int start) {
	if (visited[start] == -1) {
		visited[start] = RED;
	}
	for (int i = 0; i < vt[start].size(); i++) {
		int idx = vt[start][i];
		if (visited[idx] == -1) {
			if (visited[start] == RED) {
				visited[idx] = BLUE;
			}else if(visited[start] == BLUE) {
				visited[idx] = RED;
			}
			DFS(vt, visited, idx);
		}
		
	}
}

bool Bigraph(vector<int>(& vt)[MAX_SIZE], int* visited, int vertex) {
	for (int i = 1; i <= vertex; i++) {
		if (visited[i] == -1) {
			DFS(vt, visited, i);
		}
	}
	
	for (int i = 1; i <= vertex; i++) {
		for (int j = 0; j < vt[i].size(); j++) {
			int idx = vt[i][j];
			if (visited[i]!=-1 && visited[i] == visited[idx]) {
				return false;
			}
		}
	}
	return true;
}


int main() {
	
	int TestCase;
	cin >> TestCase;

	for (int i = 0; i < TestCase; i++) {
		int vertex;
		int edge;
		cin >> vertex >> edge;
		vector<int> vec[MAX_SIZE];
		int* visited = new int[vertex+1];
		memset(visited, -1, sizeof(int) * (vertex + 1));
		for (int j = 0; j < edge; j++) {
			int v1, v2;
			cin >> v1 >> v2;
			vec[v1].push_back(v2);
			vec[v2].push_back(v1);
		}

		if (Bigraph(vec, visited,vertex) == false) {
			cout << "NO\n";
		}
		else {
			cout << "YES\n";
		}
	}

	
	return 0;
}

 

cf. 예외 케이스

: 다음과 같이 연결되어 있지 않는 노드의 경우를 고려하여 visited 배열의 값이 -1인 한해서 모든 노드에 대해 DFS를 수행하도록 코드를 짜야함

bool Bigraph(vector<int>(& vt)[MAX_SIZE], int* visited, int vertex) {
	for (int i = 1; i <= vertex; i++) {
		if (visited[i] == -1) {
			DFS(vt, visited, i);
		}
	}
}