개요

백준 1707 : 이분 그래프

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

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

접근 방식

1. 이분 그래프에 대해 몰랐다.
   정점의 집합을 둘로 분할한다길래 일단 유니온 파인드 문제는 아니고 DFS 문제같았다.

2. 둘로 분핧했을 때, 각 집합에 속한 정점끼리는 인접하지않도록 분할한다길래
   단순 싸이클 체크인가 싶기도 했는데 그것도 문제에 부합하진 않았다.

3. 위키백과를 보니 이분 그래프는 각 edge에 포함된 두 node가 다른 색이면 된다고 한다.
   따라서 같은 edge의 두 노드가 다른 집합이여야 한다고 한다.

4. 따라서 color배열을 0을 기준으로 두고 각 노드마다 1과 -1로 구분하며 구현했다.

전체 코드

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

vector<int> v[200'01];
int color[20'001];
bool visited[20'001];

//
void DFS(int node, int tmpColor) {
	visited[node] = true;
	color[node] = tmpColor;

	for (int elem : v[node]) {
		if (visited[elem]) continue;
		
		DFS(elem, -tmpColor);
	}
}

bool IsBipartite(int nodeCnt) {
	for (int i = 1; i <= nodeCnt; i++) {
		for (int tmpNode : v[i]) {
			if (color[i] == color[tmpNode])
				return false;
		}
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int testCaseCnt = 0 , eachNode=0, eachEdge=0, tmpVertex1, tmpVertex2;
	cin >> testCaseCnt;
	for (int i = 0; i < testCaseCnt; i++) {
		cin >> eachNode >> eachEdge;
		if (eachNode == 1) {
			cout << "NO\n";
			continue;
		}
		//init
		for (int i = 0; i < 20001; i++) {
			v[i].clear();
		}
		fill(&visited[0], &visited[20001], false);
		fill(&color[0], &color[20001], 0);

		for (int j = 0; j < eachEdge; j++) {
			cin >> tmpVertex1 >> tmpVertex2;
			v[tmpVertex1].push_back(tmpVertex2);
			v[tmpVertex2].push_back(tmpVertex1);
		}

		// there could be multiple component of tree
		for (int i = 1; i < eachNode + 1; i++) {
			if(color[i]==0) 
			DFS(i, 1);
		}

		if (IsBipartite(eachNode)) cout << "YES\n";
		else cout << "NO\n";

	}
}