[BOJ] 1707. 이분그래프 (bipartite_graph, dfs, bfs)

Gold IV

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

1707번: 이분 그래프

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

 

input:

• 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다.
• 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다.
• 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다.

output:

• K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

 

---

Idea :

• 이분그래프 인지 확인하는 방법
  1. tree이거나 even cycle 일 경우 이분그래프 → odd cycle (cycle을 잇는 edge의 개수가 홀수) 인지 확인
  2. 각 edge의 양 끝 vertex가 같은 그룹이 아니어야 함 → 각 edge의 양 끝 vertex의 그룹이 다른지 확인

 

 

Code 1: check odd cycle   

• union-find를 이용해 cycle 여부를 확인
• cycle일 경우, bfs를 이용해 그래프를 따라가며 cycle을 잇는 edge의 개수를 확인

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<int> parent;
vector<int> G[20000];

int my_find(int x) {
	if (parent[x] == x) return x;
	return parent[x] = my_find(parent[x]);
}

void my_union(int a, int b) {
	int p_a = my_find(a), p_b = my_find(b);
	(p_a < p_b) ? parent[b] = p_a : parent[a] = p_b;
}

bool check_cycle(int a, int b) {
	if (my_find(a) == my_find(b)) return true;
	return false;
}

bool check_Bipartite(int a, int b) {
	if (!check_cycle(a, b)) return true;
	
	queue<pair<int, int>> Q;
	bool ch[20001] = {};

	Q.push(make_pair(a, 1));
	ch[a] = true;

	while (!Q.empty()) {
		int cur_v = Q.front().first;
		int cur_cnt = Q.front().second;
		Q.pop();

		if (cur_v == b)
			return (cur_cnt % 2 == 1) ? false : true;

		for (auto e : G[cur_v]) {
			if (ch[e]) continue;
			Q.push(make_pair(e, cur_cnt+1));
			ch[e] = true;
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	// freopen("input.txt", "rt", stdin);

	int K;
	cin >> K;
	
	while (K--) {
		/* init */
		parent.clear();
		for (int i=0; i<=20000; i++) 
			G[i].clear();

		/* input */
		int V, E;
		cin >> V >> E;
		for(int i=0; i<=V; i++)
			parent.push_back(i);

		/* solve */
		int a, b;
		bool isBipartite = true;
		while (E--) {
			cin >> a >> b;
			if (!isBipartite) continue;
			if (!check_Bipartite(a, b))
				isBipartite = false;
			G[a].push_back(b);
			G[b].push_back(a);
			my_union(a, b);
		}

		/* print answer */
		(isBipartite) ? cout << "YES\n" : cout << "NO\n";
	}	
}

 

Code 2: check vertcies' group of each edge

• bfs를 이용해 edge로 연결되어 있는 모든 vertecies의 그룹을 확인
  • 현재 vertex와 edge로 연결되어 있는 모든 vertex의 그룹을 확인
    
    • 같은 그룹이면 이분그래프가 아님, 더 이상 체크할 필요가 없으므로 빠져나옴
    • 다른 그룹이면 아직까진 이분그래프임
    • 아직 그룹이 특정되지 않았으면 현재 vertex의 그룹과 다른 그룹으로 지정
  • 현재 vertex와 연결되어 있는 모든 vertecies에 대해 위 동작을 반복
  • 이분그래프가 아님을 확인하여 중간에 빠져나오지 않고 모든 vertecies의 그룹을 확인했다면 이분그래프임

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define INIT 0
#define A 1
#define B -1

/* solve: idx vertex가 속한 그래프가 이분그래프인지 확인하는 함수 
 *
 * parameters - G: 그래프 정보
 *            - color: 각 vertex의 그룹(색) 정보
 * return - 이분그래프이면 true, 아니면 false
 */
bool solve(vector<vector<int>> G, vector<int> &color, int idx) {
	queue<int> Q;
	Q.push(idx);
	color[idx] = A;

	while (!Q.empty()) {
		int cur_i = Q.front(); Q.pop();

		for (auto e : G[cur_i]) {
			if (color[cur_i] == color[e])	// edge의 양 끝 vertex가 같은 그룹에 속함
				return false;
			else if (color[e] == INIT) {	// INIT일 경우 이전에 그룹 체크를 하지 않았음을 의미, bfs의 체크배열의 기능 겸함
				color[e] = -color[cur_i];
				Q.push(e);
			}
		}
	}
	return true;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	// freopen("input.txt", "rt", stdin);

	int K;
	cin >> K;
	
	while (K--) {
		/* input */
		int V, E, v1, v2;
		cin >> V >> E;
        
		vector<vector<int>> G(V+1);
		vector<int> color(V+1, INIT);
		while (E--) {
			cin >> v1 >> v2;
			G[v1].push_back(v2);
			G[v2].push_back(v1);
		}

		/* solve */
		bool isBipartite = true;
		// 하나의 연결그래프가 아닐 경우, 모든 그래프를 확인하기 위함 
		for (int i=1; i<=V; i++) {
			if (color[i] == INIT) {
				isBipartite = solve(G, color, i);
				if (!isBipartite) break;
			}
		}
        
        /* print answer */
		(isBipartite) ? cout << "YES\n" : cout << "NO\n";
	}

---

Result : 

Code 1) 시간초과

Code 2) 메모리: 7896 KB,  시간: 1920 ms

 

Review :

• union - find를 이용해 풀 수 있을 것이라고 생각했으나 시간, 메모리 초과...
• 논리적으로는 맞는 것 같은데 odd cycle인지 확인하는 부분이 문제이지 않을까...
• bfs를 이용하는 방법도 생각보다 너무 많은 시간이 소요됨
• 더 효과적인 방법을 찾아보자!