[백준] 1707 이분그래프

문제 요약

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

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

아이디어

그래프 탐색을 하면서 depth가 짝수인지 홀수인지를 검사한다.

depth가 짝수인 정점끼리, depth가 홀수인 정점끼리 같은 그룹으로 매핑할 수 있기 때문이다.

주의할점

그래프의 component가 하나가 아니고 여러개일 수도 있으니 미방문된 정점을 시작점으로 다시 뽑아 bfs를 진행한다.

실수했던 점

미방문된 정점을 시작점(seed)으로 다시 뽑는 과정을 1번부터 linear 하게 진행했다.
그런데 정점 개수가 워낙 많기 때문에 component를 형성하지 않는?(자신 혼자만이 component인) 정점들도 많이 있다. 이런 정점을 만났을 때 또 다시 1번부터 seed뽑기를 진행한다면 극단적인 경우에는 (시그마 i=1~n i) = O(N^2)의 time complexity가 발생한다.
BFS를 하는 데에 O(N+E)만큼의 비용이 발생해야하는데 문제가 원하는 범위를 벗어난다.

코드 cpp

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

vector<int> g[20001];
int visited[20001];
void init_graph(int sz) {
	for (int i = 1; i <= sz; i++) {
		visited[i] = 0;
		g[i] = vector<int>();
	}
}
int get_pivot(int sz) {
	for (int i = 1; i <= sz; i++) {
		if (visited[i] == 0&&!g[i].empty()) {
			return i;
		}
	}
	return -1;
}

int check(int c,int m) {
	//child 체크
	if (visited[c] != 0) {
		if (visited[c] % 2 == m % 2) {
			return -1;
		}
		return 0;
	}
	return 1;
}

bool bfs(int s) {
	bool is_bip = true;
	queue<int> q;
	q.push(s);
	visited[s] = 1;

	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		//cout << cur <<" : "<< visited[cur] << endl;
		for (int i = 0; i < g[cur].size(); i++) {
			int child = g[cur][i];
			int child_valid = check(child, visited[cur]);
			//cout << child << "child valid : " << child_valid << endl;
			if (child_valid==1) {
				q.push(child);
				visited[child] = visited[cur] + 1;
			}
			if (child_valid == -1) {
				is_bip = false;
				break;
			}
		}
	}
	return is_bip;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	cin >> t;
	for (int ctr = 0; ctr < t; ctr++) {
		int v, e;
		cin >> v >> e;
		init_graph(v);
		for (int c2 = 0; c2 < e; c2++) {
			int a, b;
			cin >> a >> b;
			g[a].push_back(b);
			g[b].push_back(a);
		}
		//cout << "done getting a graph" << endl;
		//문제점 : 컴포넌트가 하나가 아닐 수도 있다.

		bool is_bip = true;
		int seed;
		while ((seed = get_pivot(v)) != -1) {
			//cout <<"seed: "<< seed << endl;
			is_bip = bfs(seed);
			if (!is_bip) {
				break;
			}
		}
		cout << (is_bip ? "YES" : "NO") << endl;
	}
}