[자료구조] 이분 그래프 (Bipartite Graph)

이분 그래프란?

---

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

결과적으로 그래프의 모든 정점들이 두 개의 그룹으로 나눠진다.

 

 

해당 그래프가 이분 그래프인지 확인하기 위한 탐색 알고리즘으로 DFS와 BFS가 있다.

#include <iostream>
#include <vector>
using namespace std;

int T;
vector<int> a[20001];
int color[20001]; // 인접한 정점이 서로 다른 색인지 구분하기 위해 1과 2의 값만 저장한다.

void dfs(int node, int cnt) {
	color[node] = cnt;

	for (int i = 0; i < a[node].size(); i++) {
		int next = a[node][i];

		if (color[next] == 0) {
			dfs(next, 3 - cnt);
		}
	}
}

int main(void) {
	cin >> T;

	while (T--) {
		int v, e; // V = 정점의 개수, E = 간선의 개수
		cin >> v >> e;

		// 초기화
		for (int i = 1; i <= v; i++) {
			a[i].clear();
			color[i] = false;
		}

		for (int i = 0, c, d; i < e; i++) {
			cin >> c >> d;
			a[c].push_back(d);
			a[d].push_back(c);
		}

		for (int i = 1; i <= v; i++) {
			if (color[i] == 0) {
				dfs(i, 1);
			}
		}

		bool flag = true;
		for (int i = 1; i <= v; i++) {
			for (int j = 0; j < a[i].size(); j++) {
				int idx = a[i][j];

				// i번 정점이 가지는 간선에 대해 같은 값을 가지는게 있다면 이분 그래프가 아니다.
				if (color[i] == color[idx]) flag = false;
			}
		}

		if (flag) cout << "YES\n";
		else cout << "NO\n";
	}

	return 0;
}

 

 

 

참고자료

---

[1] https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html