BOJ 1707 이분 그래프

문제출처 : https://www.acmicpc.net/problem/1707

1. 문제요약

- 이분 그래프 인지 판별

- 1 <= V <= 20,000

- 1 <= E <= 200,000

2. 접근방법

- 한 정점을 방문했을 때 색깔(1, -1)을 칠해서 인접 정점들과 색이 다른지 확인

-    1(1)

      |

     2(-1)

   ／     ＼

  3(1) ― 4(1)

- 이분 그래프 판별방법

  색이 칠해진 정점을 방문한 경우 현재 정점과 인접 정점의 색이 같다면 이분 그래프가 아님

                                                                            색이 다르다면 이분 그래프임

3. 시간복잡도

- O(VE) = 4,000,000,000

4. 회고

- 이분 그래프 판별방법 자체를 몰랐음...

소스코드 : bfs

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

int t, v, e;
vector<vector<int> > g;
vector<int> check;

bool bfs(){
	queue<int> q;
	for (int i = 1; i <= v; i++){
		if (check[i] == 0){
			q.push(i);
			check[i] = 1;

			while (!q.empty()){
				int now = q.front();
				q.pop();

				for (int j = 0; j < g[now].size(); j++){
					if (check[g[now][j]] == 0){
						q.push(g[now][j]);
						check[g[now][j]] = ~check[now] + 1;
					}
					else if (check[now] + check[g[now][j]] != 0){
						return false;
					}
				}
			}
		}
	}
	return true;
}

int main(void){
	cin >> t;
	while (t--){
		cin >> v >> e;
		g = vector<vector<int> >(v + 1);
		check = vector<int>(v + 1, 0);
		int a, b;
		for (int i = 0; i < e; i++){
			cin >> a >> b;
			g[a].push_back(b);
			g[b].push_back(a);
		}

		if (bfs()) cout << "YES" << "\n";
		else cout << "NO" << "\n";
	}
	return 0;
}

소스코드 : dfs

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

int t, v, e;
vector<vector<int> > g;
vector<int> check;

bool dfs(int now, int c){
	check[now] = c;

	for (int i = 0; i < g[now].size(); i++)
		if (check[g[now][i]] == 0){
			if (!dfs(g[now][i], -c))
				return false;
		}
		else if (check[now] == check[g[now][i]])
			return false;
	return true;
}

int main(void){
	cin >> t;
	while (t--){
		cin >> v >> e;
		g = vector<vector<int> >(v + 1);
		check = vector<int>(v + 1, 0);
		int a, b;
		for (int i = 0; i < e; i++){
			cin >> a >> b;
			g[a].push_back(b);
			g[b].push_back(a);
		}

		bool isBi = true;
		for (int i = 1; i <= v; i++)
			if (check[i] == 0)
				if (!dfs(i, 1)) {
					isBi = false;
					break;
				}

		if (isBi) cout << "YES" << "\n";
		else cout << "NO" << "\n";
	}
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]