[백준] 1707번 : 이분 그래프 C++ 문제풀이 솔루션

문제

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

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

입력

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

출력

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

제한

• 2 ≤ K ≤ 5
• 1 ≤ V ≤ 20,000
• 1 ≤ E ≤ 200,000

예제 입력 1

2
3 2
1 3
2 3
4 4
1 2
2 3
3 4
4 2

예제 출력 1

YES
NO

 

 

이분 그래프는 인접한 노드가 같은 집합에 속해 있지 않은 그래프입니다.

모든 인접한 노드가 서로 다른 색으로 칠해져 있다면 이분 그래프입니다.

트리는 항상 이분 그래프입니다.

이분 그래프

 

각 정점마다 dfs로 탐색하여 이분 그래프 여부를 확인합니다.

이 때, 각 집합은 1과 2로 visited에 저장됩니다.

dfs로 탐색을 진행하므로 한 번 방문한 정점은 다시 방문할 필요가 없습니다.

이분 그래프가 아닌 것으로 확인된 그래프는 더 이상 확인 할 필요가 없습니다.

#include <iostream>
#include <vector>
#include <algorithm>

#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false)

using namespace std;

vector<vector<int>> graph;
vector<int> visited; //미방문 0, 집합 1,2
vector<bool> vis;
bool type;

void dfs(int node, int set) {
  if (set == visited[node]) {
	type = false;
	return;
  }
  if (visited[node] == 0) {
	if (set == 1) visited[node] = 2;
	else if (set == 2) visited[node] = 1;
	vis[node] = true;
	for (auto& i : graph[node])
	  dfs(i, visited[node]);
  } else return;
}
int main() {
  fast_io;
  int k;
  cin >> k;
  for (int i = 0; i < k; i++) {
	int v, e;
	cin >> v >> e;
	graph.clear();
	visited.clear();
	vis.clear();
	graph.resize(v + 1);
	visited.resize(v + 1, 0);
	vis.resize(v + 1, false);
	type = true;
	for (int j = 0; j < e; j++) {
	  int a, b;
	  cin >> a >> b;
	  graph[a].push_back(b);
	}
	for (int j = 1; j <= v; j++) {
	  if (!type) break;
	  if (vis[j]) continue;
	  dfs(j, 1);
	  fill(visited.begin(), visited.end(), 0);
	}
	if (type) cout << "YES" << '\n';
	else cout << "NO" << '\n';
  }
  return 0;
}