[백준] 이분 그래프 (1707번)

문제

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

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

입력

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

출력

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

---

이분 그래프인지 아닌지를 판별하는 문제이다.

이분 그래프를 판별하는 방법은 단순하다.

내가 방문하는 지점에 나랑 다른 값을 계속 넣어주는 것이다. 

만약 나랑 인접한 노드가 나와 같은 값을 갖는다면 이 그래프는 이분 그래프가 아니다.

bfs를 이용해서 각 지점마다 방문하며 값을 확인해주자.

 

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EC%9D%B4%EB%B6%84%20%EA%B7%B8%EB%9E%98%ED%94%84%20(1707%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
int T, N, M;
bool isTrue;
int visit[20002];
vector<int> map[20002];

void bfs(int start) {
	queue<int> q;
	q.push(start);
	visit[start] = 1;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = 0; i < map[x].size(); i++) {
			int nx = map[x][i];
			if (visit[nx] == 0) {
				q.push(nx);
				visit[nx] = 3 - visit[x];
			}
			else if (visit[nx] == visit[x] && visit[nx] != 0) {
				isTrue = false;
				return;
			}
		}
	}
}

int main()
{
	cin >> T;
	while (T--) {
		cin >> N >> M;

		isTrue = true;
		memset(visit, 0, sizeof(visit));
		memset(map, 0, sizeof(map));

		for (int a, b, i = 0; i < M; i++) {
			cin >> a >> b;
			map[a].push_back(b);
			map[b].push_back(a);
		}

		for (int i = 1; i <= N; i++) {
			if (visit[i] == 0)
				bfs(i);
			if (!isTrue) break;
		}
		
		if (isTrue)
			cout << "YES\n";
		else
			cout << "NO\n";
	}
}