[백준] 알고리즘 1707번 - 이분 그래프문제

문제

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

1707번: 이분 그래프

소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include<memory.h>
using namespace std;
vector<int> g[20001];
int check[20001];
void dfs(int index) {
	int size = g[index].size();
	for (int i = 0; i < size; i++) {
		int next = g[index][i];
		if (check[next] == 0) {
			if (check[index] == 1) {
				check[next] = 2;
			}
			else {
				check[next] = 1;
			}
			dfs(next);
		} 
	}
	 
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		int v, e;
		cin >> v >> e;
		for (int i = 0; i < e; i++) {
			int x, y;
			cin >> x >> y;
			g[x].push_back(y);
			g[y].push_back(x);
		}
		for (int i = 1; i <= v; i++) {
			if (check[i] == 0) {
				check[i] = 1;
				dfs(i);
			}
		}
		bool flag = true;
		for (int i = 1; i <= v; i++) {
			for (int j = 0; j < g[i].size(); j++) {
				if (check[i] == check[g[i][j]]) {
					flag = false;
					break;
				}
			}
		}
		if (flag) cout << "YES";
		else cout << "NO";
		cout << "\n";
		memset(g, 0, sizeof(g));
		memset(check, 0, sizeof(check));
	}
}

해설

이분그래프는 저렇게 1번구역 2번구역을 세로로 나눴을 때, 1번구역에 있는 정점들은 1번끼리 연결되었다면 이분 그래프라고 할 수 없다.

구역을 체크할 수 있는 배열을 만들어줘야한다.

체크배열을 int형으로 받아서 0이면 아에 방문하지않음, 1이면 1번구역방문 2면 2번구역 방문이라 생각하고 요소를 저장해줘야 한다.

소스코드를 보면 좀 더 이해하기 쉬울 것이다.

bfs로 해결한 코드를 올려드리겠습니다, 둘다 숙지하면 좋을 것 같습니다.

https://github.com/kitten-master/algorithm/commit/0d5aea31a8a4bb116782af5be16ab63c9d2947a3

이분 그래프(bfs add) · kitten-master/algorithm@0d5aea3