#1707번 이분 그래프 (C++)

링크 : www.acmicpc.net/problem/1707

1707번: 이분 그래프

예전에 Union & Find 알고리즘과 관련하여 유사 문제로 풀어본 경험이 있는 문제다.

문제 해석이 난해할 수 있는데, 한 줄로 요약하면 2가지 색으로 서로 연결된 노드끼리 겹치지 않게 칠할수 있는가를 묻는 문제이다.

 

가능하다

불가능하다

 

 

문제 풀이는 다음과 같다. 

1. 방향성이 정해지지 않은 노드, 즉 양방향 노드이다.

때문에 1번과 3번이 연결되어있으면 3번과 1번도 연결되어있다는 뜻이므로,

배열[1]에 3을 저장하고, 배열[3]에 1을 저장한다.

2. DFS를 시작한다. 이때 조건은 int로 선언한 색깔이 비어있는 경우에만 DFS를 진행한다. 

3. DFS를 진행해서 해당 노드에 연결된 다음 노드에 겹치지 않는 색을 칠해준다.

4. DFS가 종료되고, 색이 겹치지 않는지를 판단한다.

즉, 한 노드에 연결된 다음 노드가 서로 색이 겹치지 않으면 된다. 

 

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#define SIZE 20001

using namespace std;

int t, v, e, a, b;
int ch[SIZE];
vector<int> arr[SIZE];

void dfs(int num, int  color) {
	ch[num] = color;
	for (int i = 0; i < arr[num].size(); i++) {
		int next = arr[num][i];
		if (!ch[next]) dfs(next, 3 - color); // 이렇게 해서 1, 2, 1, 2, 를 반복 색칠
	}
}

bool check() {
	for (int i = 1; i <= v; i++) {
		for (int j = 0; j < arr[i].size(); j++) {
			int next = arr[i][j];
			if (ch[next] == ch[i]) return false; // 서로 연결되어있는 간선 조합 (ex : 1-2)
		}
	}
	return true;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> t;
	while(t>0){
		cin >> v >> e;
		for (int j = 0; j < e; j++) {
			cin >> a >> b;
			arr[a].push_back(b);
			arr[b].push_back(a);
		}
		for (int j = 1; j <= v; j++) {
			if (!ch[j]) dfs(j, 1); // 색칠하러 가자
		}
		if (!check()) cout << "NO" << "\n";
		else cout << "YES" << "\n";
		//초기화 과정
		memset(ch, 0, sizeof(ch));
		for (int a = 1; a < SIZE; a++) arr[a].clear();
		t--;
	}
	return 0;
}