글 읽기 - [1707] 이분 그래프 모든 반례, 모든 경우 다 맞는 것 같은데.. 제발요

sllover95 2년 전 0

제목 그대로 모든 경우의 수 다 해본 것 같은데 틀립니다.. 도와주세요

#define _CRT_SECURE_NO_WARNINGS
#define MAX_VERTEX_NUM 20001
#include <stdio.h>
#include <stdlib.h>

int color[MAX_VERTEX_NUM];

/* 그래프 정점 구조체 */
typedef struct GraphNode {
	int v_id;                  // 정점
	struct GraphNode* next;    // 다음 정점
}GraphNode;

/* 그래프 전체 구조체 */
typedef struct GraphType {
	int v_num;                 // 정점의 개수
	GraphNode* adj[MAX_VERTEX_NUM];
}GraphType;

GraphType graph;

/* 그래프 초기화 함수 */
void InitGraph(GraphType* g, int v_cnt) {

	/* 정점의 개수 및 연결, 색 초기화 */
	g->v_num = v_cnt;
	for (int i = 1; i <= v_cnt; i++) {
		g->adj[i] = NULL;
		color[i] = 0;
	}
}

/* u -> v 간선 추가 함수 */
void InsertEdge(GraphType* g, int u, int v) {

	/* 새로운 노드 생성 */
	GraphNode* node = (GraphNode*)malloc(sizeof(GraphNode)); 

	/* 새로운 노드 정보 할당 및 연결 */
	node->v_id = v;            
	node->next = g->adj[u];       
	g->adj[u] = node;
}

/* 이분 그래프 확인 함수 */
int IsBipartiteGraph(GraphType* g) {
	int bp = 1;
	GraphNode* p;

	/* 모든 노드 검사 */
	for(int i = 1; i <= g->v_num; i++) {

		if (color[i] == 0)
			color[i] = -1;

		/* 현재 노드에서 인접노드 탐색 */
		p = g->adj[i];

		while (p != NULL) {

			/* 칠하지 않은 노드는 칠하기 */
			if (color[p->v_id] == 0) 
				color[p->v_id] = (color[i] * -1);
		
			/* 인접노드가 같은 색이면 이분 그래프가 아님 */
			else if (color[p->v_id] == color[i] || p->v_id == i) 
				bp = 0;

			p = p->next;
		}
	}

	return bp;
}

/* 그래프 출력 함수 */
void print_adj_list(GraphType* g) {
	GraphNode* p;
	for (int i = 1; i <= g->v_num; i++) {
		p = g->adj[i];
		printf("정점 %d의 인접노드: ", i);
		while (p != NULL) {
			printf("%d ", p->v_id);
			p = p->next;
		}
		printf("\n");
	}
}


int main() {
	int k, v, e;
	int node1, node2;

	scanf("%d", &k);

	while (k--) {
		scanf("%d %d", &v, &e);
		
		InitGraph(&graph, v);

		for (int i = 0; i < e; i++) {
			scanf("%d %d", &node1, &node2);

			/* 사이클 = 하나만 삽입 */
			if (node1 == node2) {
				InsertEdge(&graph, node1, node2);
				continue;
			}

			/* 무방향 그래프 = 양쪽 다 삽입 */
			InsertEdge(&graph, node1, node2);
			InsertEdge(&graph, node2, node1);
		}

		if(IsBipartiteGraph(&graph))
			printf("YES\n");
		else
			printf("NO\n");

		print_adj_list(&graph);
		for (int i = 1; i <= v; i++)
			printf("%d: %d색\n", i, color[i]);
	}

	return 0;
}

dogeee 2년 전 2

게시판 9쪽에 있는 글에서 반례 찾았습니다.

https://www.acmicpc.net/board/...

1
6 6
1 3
3 4
4 2
2 5
5 6
6 1

출력: NO

답: YES

sllover95 2년 전 1

사랑합니다...

이 코드의 문제점은 1부터 v개의 정점까지 "순서대로" 검사하기 때문에 위의 반례에서

1) 1의 인접 정점 3과 6을 칠하고

2) 2의 인접 정점 4와 5를 칠하기 때문에

나중에 서로 만났을 때 색이 겹치는군요.. 사실상 DFS도 아니구요

그래서 고친 코드가

처음에 main에서 코드를 돌릴 때 시작할 노드를 칠하고 DFS로 확인한 후

또 안 칠해져있는 시작 노드를 찾아 비연결 그래프도 가능하게 만들었습니다.

정말 감사합니다.

#define _CRT_SECURE_NO_WARNINGS
#define MAX_VERTEX_NUM 20001
#include <stdio.h>
#include <stdlib.h>

int color[MAX_VERTEX_NUM];  // 색
int bp;                     // 이분 그래프 확인 변수

/* 그래프 정점 구조체 */
typedef struct GraphNode {
	int v_id;                  // 정점
	struct GraphNode* next;    // 다음 정점
}GraphNode;

/* 그래프 전체 구조체 */
typedef struct GraphType {
	int v_num;                 // 정점의 개수
	GraphNode* adj[MAX_VERTEX_NUM];
}GraphType;

GraphType graph;

/* 그래프 초기화 함수 */
void InitGraph(GraphType* g, int v_cnt) {

	/* 정점의 개수 및 연결, 색 초기화 */
	g->v_num = v_cnt;
	for (int i = 1; i <= v_cnt; i++) {
		g->adj[i] = NULL;
		color[i] = 0;
	}
}

/* u -> v 간선 추가 함수 */
void InsertEdge(GraphType* g, int u, int v) {

	/* 새로운 노드 생성 */
	GraphNode* node = (GraphNode*)malloc(sizeof(GraphNode)); 

	/* 새로운 노드 정보 할당 및 연결 */
	node->v_id = v;            
	node->next = g->adj[u];       
	g->adj[u] = node;
}

/* 이분 그래프 확인 함수 */
void CheckBipartiteGraph(GraphType* g, int s_node) {
	GraphNode* p;

	/* 현재 노드에서 인접노드 탐색 */
	p = g->adj[s_node];

	/* 현재 노드의 인접노드 색 검사 */
	while (p != NULL) {

		/* 칠하지 않은 노드는 칠하기 */
		if (color[p->v_id] == 0) {
			color[p->v_id] = (color[s_node] * -1);
			CheckBipartiteGraph(g, p->v_id);
		}

		/* 인접노드가 같은 색이면 이분 그래프가 아님 */
		else if (color[p->v_id] == color[s_node])
			bp = 0;

		/* 다음 인접노드로 */
		p = p->next;
	}
}

/* 그래프 출력 함수 */
void print_adj_list(GraphType* g) {
	GraphNode* p;
	for (int i = 1; i <= g->v_num; i++) {
		p = g->adj[i];
		printf("정점 %d의 인접노드: ", i);
		while (p != NULL) {
			printf("%d ", p->v_id);
			p = p->next;
		}
		printf("\n");
	}
}


int main() {
	int k, v, e;
	int node1, node2;

	scanf("%d", &k);

	while (k--) {
		bp = 1;

		scanf("%d %d", &v, &e);
		
		InitGraph(&graph, v);

		for (int i = 0; i < e; i++) {
			scanf("%d %d", &node1, &node2);

			/* 자기자신 사이클 = 하나만 삽입 */
			if (node1 == node2) {
				InsertEdge(&graph, node1, node2);
				continue;
			}

			/* 무방향 그래프 = 양쪽 다 삽입 */
			InsertEdge(&graph, node1, node2);
			InsertEdge(&graph, node2, node1);
		}

		/* 비연결 & 연결 그래프 모두 검사 */
		for (int i = 1; i <= v; i++) {
			if (color[i] == 0) {
				color[i] = -1;
				CheckBipartiteGraph(&graph, i);
			}
		}

		/* 이분 그래프 여부 출력 */
		if(bp)
			printf("YES\n");
		else
			printf("NO\n");

	}

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[1707] 이분 그래프 모든 반례, 모든 경우 다 맞는 것 같은데.. 제발요

sllover95 2년 전 0

dogeee 2년 전 2

sllover95 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말