[Algorithm][C++] BOJ 1707: 이분 그래프

url: https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

 

풀이 핵심

1. dfs/bfs 문제

 

2. 문제는 매우 간단하지만 Pro 시험에서 Linked List 자료구조는 필수로 구현할 줄 알아야 하므로 Linked List를 이용해 풀이해보고자 한다. 이 문제는 바이러스 문제와 달리 초기화를 해줘야 한다. linked list 구현은 바이러스 문제와 같고 (Tail 포인터를 사용하지 않고) 초기화 함수만 추가된 것이다.

 

3. linked list 구현은 바이러스 문제에서 확인해보자. dfs 구현은 코드에서 확인해 보자.

 

코드

#include <cstdio>
#define MAXV	20001
#define MAXE	200000

int K, V, E;
struct NODE {
	int node;
	NODE* next;
};

NODE HEAD[MAXV];
NODE POOL[MAXE * 2];
int check[MAXV];
int pcnt;

void init() {
	pcnt = 0;
	for (int i = 1; i <= V; i++) HEAD[i].next = 0, check[i] = 0;
}

void make(int p, int c) {
	NODE* nd = &POOL[pcnt++];
	nd->node = c;

	nd->next = HEAD[p].next;
	HEAD[p].next = nd;
}

int dfs(int node, int color) {
	check[node] = color;

	for (NODE* p = HEAD[node].next; p; p = p->next) {
		if (check[p->node] == color) return 0;
		if (!check[p->node]) {
			if (!dfs(p->node, 3 - color)) return 0;
		}
	}

	return 1;
}

int main() {
	scanf("%d", &K);
	for (int tc = 1; tc <= K; tc++) {
		int flag;
		scanf("%d %d", &V, &E);
		init();
		for (int i = 0; i < E; i++) {
			int p, c;
			scanf("%d %d", &p, &c);
			make(p, c);
			make(c, p);
		}
		for (int i = 1; i <= V; i++) {
			if (check[i] == 0) {
				flag = dfs(i, 1);
				if (!flag) break;
			}
		}

		if (flag) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}