[C/C++] 백준 - 1707번 : 이분 그래프

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

1707번: 이분 그래프

전에 풀었었던 문제이지만, 까먹어서 한 번 다시 풀어보았다. 전에는 BFS로 풀었는데

오늘은 DFS로 풀어봤다. 개인적으로 BFS보다 DFS코드가 더 명료하고 이해하기 쉬웠다.

 

아직 방문처리가 되지 않은 노드가 존재하면 그 노드로부터 시작한다. 

그 노드에 색칠을 해주고 난 후 다음 색깔을 정해준다. 나는 처음 노드로 들어갈 경우 1로 색깔을 지정해주었고, 다음 

색깔은 현재 색깔이 1이면 2, 2면 1인 식으로 2가지 색만을 이용한다.

 

첨 노드로부터 연결된 노드가 아직 색칠이 되지 않았다면 똑같이 색깔을 칠해주기 위해 DFS로 실행한다.

근데 연결된 노드 중 색칠이 된 노드가 존재하면 그 노드의 색깔을 확인하고 현재와 색깔이 같은 노드라면 이 그래프는 이분그래프가 아니다 라고 판정해준다.

 

#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <bitset>
#define INF 987654321
#define Mod 9901
#define CUNLINK ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
#define ll long long
#define ENDL cout << endl
#define endl '\n'

using namespace std;
typedef struct GraphNode {
	int cost;
	int dest;
	GraphNode* next;
}GraphNode;

typedef struct Graph {
	int cnt;
	GraphNode* adj;
}Graph;

int V, E;
int visited[20001];
int Color[20001];
bool isBinary = false;

void Init_Graph(Graph* gph, int cnt) {
	gph->cnt = cnt;
	gph->adj = (GraphNode*)malloc(sizeof(GraphNode) * (cnt+1));
	for (int i = 1; i <= cnt; i++) gph->adj[i].next = NULL;
}

int AddDirectedLinkedEdge(Graph* gph, int src, int dst, int cost) {
	GraphNode* Temp = (GraphNode*)malloc(sizeof(GraphNode));
	Temp->cost = cost;
	Temp->dest = dst;
	Temp->next = gph->adj[src].next;
	gph->adj[src].next = Temp;
	return 1;
}

int AddUnDirectedLinkedEdge(Graph* gph, int src, int dst, int cost) {
	return AddDirectedLinkedEdge(gph, src, dst, cost) && AddDirectedLinkedEdge(gph, dst, src, cost);
}

void Reset_Graph(Graph* gph, int cnt) {
	gph->cnt = 0;
	for (int i = 1; i <= cnt; i++) {
		gph->adj[i].next = NULL;
		free(gph->adj[i].next);
	}
}

void DFS(Graph* gph, int index, int color) {
	visited[index] = color;
	int nColor;
	if (color == 1) nColor = 2;
	else nColor = 1;
	GraphNode* head = gph->adj[index].next;
	while (head) {
		if (!visited[head->dest]) {
			DFS(gph, head->dest, nColor);
		}
		else {
			if (visited[head->dest] == color) {
				isBinary = true;
				break;
			}
		}
		head = head->next;
	}
}

int main() {
	CUNLINK;
	Graph graph;
	int testCase;
	cin >> testCase;
	while (testCase--) {
		cin >> V >> E;
		Init_Graph(&graph, V);
		for (int i = 0; i < E; i++) {
			int a, b;
			cin >> a >> b;
			AddUnDirectedLinkedEdge(&graph, a, b, 1);
		}
		isBinary = false;
		for (int i = 1; i <= V; i++) {
			if (!visited[i])
				DFS(&graph, i, 1);
		}
		if (!isBinary) 
			cout << "YES" << endl;
		else 
			cout << "NO" << endl;
		memset(visited, false, sizeof(visited));
		Reset_Graph(&graph, V);
	}
	return 0;
}